There are rectangles on a two-dimensional plane. The -th rectangle has a weight . You should find non-overlapping rectangles and , and make as large as possible.

rectangles are non-overlapping if and only if no points are inside both rectangles at the same time. For example, rectangles and are overlapping, as are rectangles and , but rectangles and are not overlapping.

输入描述:

The first line contains an integer  --- the number of test cases.
For each test case, the first line contains an integer  --- the number of rectangles.
Then  lines follow, each line contains  integers  --- the lower left corner  and upper right corner .
The next line contains  integers  --- the weight of the -th rectangle.
It is guaranteed that  over all test cases.

输出描述:

For each test case, output an integer in one line --- the maximum value of . If all rectangles overlap each other, output .

2
3
1 1 6 5
3 2 5 3
6 5 8 7
10 1 2
2
1 1 6 5
6 5 8 7
1 2

3
-1