众所周知,重大虎溪校区有两个最大的食堂,一食堂和二食堂。每天去哪里吃饭是一个令人难以做出选择的问题。某一天午饭时间,有个学生即将下课去吃饭,他们位于学校的各个方位,面临着是去一食堂还是二食堂的问题。每一个学生吃饭都是有要求的,必须和他喜欢的人在一个食堂,不喜欢的必须在两个食堂,这样才能吃的舒服。。。如何安排才能满足这个要求并且安排使得任意两人走过的距离加上二人所在食堂的距离的最大值最小。为了简化问题,我们把学校抽象成一个二维坐标系,距离为曼哈顿距离。

输入第一行有一个,表示样例个数。
每个样例一行3个整数表示有个人,对人互相讨厌,对人相互喜欢。
接下来一行四个整数表示一食堂和二食堂的坐标。
接下来行,每行个整数代表每一个人的坐标。
接下来行,每行个整数,表示二者互相讨厌。
接下来行,每行个整数,表示二者互相喜欢。

每一个样例输出一行。
输出最大的距离,如果无法满足条件则输出

3
3 0 1
0 0 0 1
0 1
0 -1
-1 0
1 2
4 1 1
12750 28546 15361 32055
6706 3887
10754 8166
12668 19380
15788 16059
3 4
2 3
3 3 0
0 0 0 1
0 5
5 0
5 5
1 2
2 3
1 3

2
53246
-1

对于样例1,三个人都在一个是食堂的话,任意两人走过的距离为2,任意两人所在食堂的距离为0,所以答案是2。