시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 7 7 35.000%

문제

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

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

지도는 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 을 만족하는 정수이다.

출력

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

예제 입력 1

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

예제 출력 1

5 0
200 250
W3sicHJvYmxlbV9pZCI6IjM3MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzdcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHViOWNjXHViMDk4XHViN2VjIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGFjXHViMjk0IFx1YWNmM1x1Yzc0MCBcdWM1YjhcdWIzNTVcdWM5YzQgXHVhY2YzXHVjNzc0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNWI4XHViMzU1XHVjNzQ0IFx1YWM3N1x1YjI5NCBcdWFjODNcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGI0XHVhY2UwXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc1OCBcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjOWMwXHViM2M0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YjBiNFx1YjgyNFx1YWMwMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YjNjNFx1YjI5NCB4eVx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCAoMCwwKSwgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCAoMTAwIDAwMCwgMClcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YjJlNFx1Yjk3OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWFjZmMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNjQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjNzA0XHVjNWQwIFx1YzBiNFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3dhbGsoMikucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgwcHg7IGxpbmUtaGVpZ2h0OjEuNmVtOyBvcGFjaXR5OjAuOTsgd2lkdGg6MzQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWM1NTVcdWNkOTVcdWQ1NzRcdWMxMWMgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKCZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzIxOCAwICZsZTsgTiAmbGU7IDIsNTAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwIEg8c3ViPmk8XC9zdWI+XHViMjk0IFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWIxOTJcdWM3NzQgKDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIFx1Yzc3NFx1YmE3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTAgUDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMyAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsZTsgMjAwMCkgXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIC4uLiwgeDxzdWI+UDxzdWI+aTxcL3N1Yj48XC9zdWI+LCB5PHN1Yj5QPHN1Yj5pPFwvc3ViPjxcL3N1Yj5cdWI4NWMgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIC0zMDAsMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMzAwLDAwMCBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWFjZmMgXHViMGI0XHViODI0XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3MDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXYWxrIiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSB3b3VsZCBsaWtlIHRvIHZpc2l0IEJvYi4gSG93ZXZlciwgdGhleSBsaXZlIGluIGEgaGlsbHkgbGFuZHNjYXBlLCBhbmQgQWxpY2UgZG9lc24mcnNxdW87dCBsaWtlIHRvIHdhbGsgaW4gaGlsbHMuIFNoZSBoYXMgYSBtYXAgb2YgdGhlIGFyZWEsIHNob3dpbmcgdGhlIGhlaWdodCBjdXJ2ZXMuIFlvdSBoYXZlIHRvIGNhbGN1bGF0ZSB0aGUgdG90YWwgYWx0aXR1ZGUgY2xpbWJlZCwgYW5kIHRoZSB0b3RhbCBhbHRpdHVkZSBkZXNjZW5kZWQsIGZvciB0aGUgcm91dGUgd2hpY2ggbWluaW1pemVzIHRoZXNlIG51bWJlcnMuIEl0IGRvZXMgbm90IG1hdHRlciBob3cgZmFyIHNoZSBoYXMgdG8gd2FsayB0byBhY2hpZXZlIHRoaXMuPFwvcD5cclxuXHJcbjxwPlNpbmNlIHlvdSBkb24mcnNxdW87dCBrbm93IHdoYXQgdGhlIGxhbmRzY2FwZSBsb29rcyBsaWtlIGluIGJldHdlZW4gdGhlIGhlaWdodCBjdXJ2ZXMsIHlvdSBjYW5ub3Qga25vdyBleGFjdGx5IGhvdyBtdWNoIGNsaW1iIGFuZCBkZXNjZW50IHNoZSB3aWxsIGFjdHVhbGx5IGdldCBpbiBwcmFjdGljZSwgYnV0IHlvdSBzaG91bGQgY2FsY3VsYXRlIHRoZSBtaW5pbXVtIHBvc3NpYmxlIHVuZGVyIG9wdGltYWwgY29uZGl0aW9ucyBiYXNlZCBvbiB3aGF0IHlvdSBjYW4gZGVkdWNlIGZyb20gdGhlIG1hcC48XC9wPlxyXG5cclxuPHA+VGhlIG1hcCBpcyByZXByZXNlbnRlZCBhcyBhbiB4eSBncmlkLiBBbGljZSBsaXZlcyBpbiAoMCwgMCksIGFuZCBCb2IgbGl2ZXMgaW4gKDEwMCAwMDAsIDApLiBUaGUgaGVpZ2h0IGN1cnZlcyBhcmUgcmVwcmVzZW50ZWQgYXMgcG9seWdvbnMsIHdoZXJlIGEgcG9seWdvbiBjYW5ub3QgaW50ZXJzZWN0IGl0c2VsZiBvciBhbm90aGVyIHBvbHlnb24uIEZ1cnRoZXJtb3JlLCBuZWl0aGVyIEFsaWNlIG5vciBCb2IgbGl2ZXMgZXhhY3RseSBvbiBhIGhlaWdodCBjdXJ2ZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93YWxrKDIpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MHB4OyB3aWR0aDozNDVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5TZWNvbmQgdGVzdCBjYXNlIGZyb20gc2FtcGxlIGlucHV0IChjb21wcmVzc2VkKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggMCAmbGU7IE4gJmxlOyAyIDUwMCwgdGhlIG51bWJlciBvZiBoZWlnaHQgY3VydmVzLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSBmb3IgZWFjaCBoZWlnaHQgY3VydmUsIHdpdGggMSAmbGU7IEg8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgYmVpbmcgdGhlIGhlaWdodCBvZiB0aGUgY3VydmUsIDMgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IDIgMDAwIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIHBvbHlnb24sIGFuZCB0aGUgdmVydGljZXMgeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCAuLi4sIHg8c3ViPlA8c3ViPmk8XC9zdWI+PFwvc3ViPiwgeTxzdWI+UDxzdWI+aTxcL3N1Yj48XC9zdWI+IGhhdmluZyBpbnRlZ3JhbCB2YWx1ZXMgJm1pbnVzOzMwMCAwMDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAzMDAgMDAwLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXJlIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDIwMCAwMDAgcG9seWdvbiB2ZXJ0aWNlcyBpbiB0b3RhbCBpbiBhbGwgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0d28gbnVtYmVyczogdGhlIHRvdGFsIGFsdGl0dWRlIGNsaW1iZWQgYW5kIHRoZSB0b3RhbCBhbHRpdHVkZSBkZXNjZW5kZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==