시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 6 6 28.571%

문제

선영이는 상근이를 만나러 가려고 한다. 두 사람이 사는 곳은 언덕진 곳이다. 선영이는 언덕을 걷는 것을 매우 싫어한다.

선영이는 두 사람이 살고있는 지역의 등고선 지도를 가지고 있다. 지도를 이용해 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 구해보려고 한다. 이 때, 두 값을 최소로 해야 한다.

지도는 xy평면으로 나타낼 수 있고, 선영이의 집은 (0,0), 상근이의 집은 (100 000, 0)에 있다. 등고선은 다각형으로 나타낼 수 있으며, 다각형이 자기 자신이 교차하거나, 다른 다각형과 교차하는 경우는 없다. 또, 선영이와 상근이가 등고선 위에 살고있는 경우는 없다.

위의 그림은 두번째 예제를 압축해서 그림으로 나타낸 것이다.

입력

첫째 줄에 테스트 케이스의 개수 T (≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 등고선의 수 0 ≤ N ≤ 2,500 이 주어지며, 다음 줄부터 N개 줄에는 등고선의 정보가 주어진다. 첫 번째 숫자 Hi는 등고선의 높이 (1 ≤ Hi ≤ 1000) 이며, 두 번째 숫자 Pi는 다각형을 이루는 꼭지점의 개수이다. (3 ≤ Pi ≤ 2000) 다음 숫자는 x1, y1, ..., xPi, yPi로 다각형의 꼭지점을 나타내며, -300,000 ≤ xi, yi ≤ 300,000 을 만족하는 정수이다.

출력

각 테스트 케이스마다 올라가야 하는 높이의 합과 내려가야 하는 높이의 합을 출력한다.

예제 입력

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

예제 출력

5 0
200 250

힌트