Walking

Time limit1sMemory limit128 MB

Summary

Given nested non-intersecting contour polygons on a plane, compute the minimum total ascent and descent along some path from one fixed point to another based on how many polygons of each height enclose the endpoints.

Level: Hard8 of 10
Topics: Geometry, Graph, Greedy
Solved: No attempts yet

Problem

Sunyoung wants to visit Sanggeun. They both live in a hilly region, and Sunyoung strongly dislikes walking up and down hills.

Sunyoung has a contour map of the region where the two of them live. Using this map, she wants to compute, for a walk from her house to Sanggeun's house, the total height she must climb and the total height she must descend, making both sums as small as possible.

The map is drawn on the xy-plane. Sunyoung's house is at (0, 0) and Sanggeun's house is at (100000, 0). Each contour line is given as a polygon. No polygon intersects itself or any other polygon, and neither house lies on any contour line.

Input

The first line contains the number of test cases T (T ≤ 100).

The first line of each test case contains the number of contour lines N (0 ≤ N ≤ 2500). Each of the next N lines describes one contour line. On each such line, the first integer Hi is the height of the contour (1 ≤ Hi ≤ 1000) and the second integer Pi is the number of vertices of the polygon (3 ≤ Pi ≤ 2000). The following integers give the vertices in the order x1, y1, x2, y2, …, xPi, yPi, where every coordinate is an integer with -300000 ≤ xi, yi ≤ 300000.

Output

For each test case, print the total height to climb and the total height to descend, separated by a single space, on one line.

Examples8

Example 1

Input

2
2
20 3 10 10 0 -10 -10 10
25 3 20 20 0 -20 -20 20
3
100 4 -1 1 1 1 1 -1 -1 -1
300 8 -2 2 2 2 2 -2 5 -2 5 1 6 1 6 -3 -2 -3
50 8 3 3 100001 3 100001 -1 7 -1 7 2 4 2 4 -1 3 -1

Expected output

5 0
200 250

Example 2
Input
```
1
0
```
Expected output
```
0 0
```
Example 3
Input
```
1
1
10 4 -5 -5 5 -5 5 5 -5 5
```
Expected output
```
0 0
```

Example 4

Input

1
1
40 4 99995 -5 100005 -5 100005 5 99995 5

Expected output

0 0

Example 5

Input

1
2
10 4 -3 -3 3 -3 3 3 -3 3
50 4 -8 -8 8 -8 8 8 -8 8

Expected output

40 0

Example 6

Input

1
2
50 4 -3 -3 3 -3 3 3 -3 3
10 4 -8 -8 8 -8 8 8 -8 8

Expected output

0 40

Example 7

Input

1
4
100 4 -2 -2 2 -2 2 2 -2 2
300 4 -6 -6 6 -6 6 6 -6 6
200 4 99994 -6 100006 -6 100006 6 99994 6
50 4 99998 -2 100002 -2 100002 2 99998 2

Expected output

200 250

Example 8

Input

1
4
7 4 -150000 -200000 250000 -200000 250000 200000 -150000 200000
100 4 -2 -2 2 -2 2 2 -2 2
250 4 -5 -5 5 -5 5 5 -5 5
30 4 99996 -4 100004 -4 100004 4 99996 4

Expected output

150 220