시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 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 을 만족하는 정수이다.

출력

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

예제 입력 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+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMGI0XHVhY2UwXHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc1OCBcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjOWMwXHViM2M0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YjBiNFx1YjgyNFx1YWMwMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI0NTAgXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWIzYzRcdWIyOTQgeHlcdWQzYzlcdWJhNzRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM3NDAgKDAsMCksIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM3NDAgKDEwMCAwMDAsIDApXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHViNGYxXHVhY2UwXHVjMTIwXHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhZDUwXHVjYzI4XHVkNTU4XHVhYzcwXHViMDk4LCBcdWIyZTRcdWI5NzggXHViMmU0XHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViNGYxXHVhY2UwXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWMwYjRcdWFjZTBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93YWxrKDIpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MHB4OyBsaW5lLWhlaWdodDoxLjZlbTsgb3BhY2l0eTowLjk7IHdpZHRoOjM0NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViNDUwXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWM1NTVcdWNkOTVcdWQ1NzRcdWMxMWMgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKCZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzIxOCAwICZsZTsgTiAmbGU7IDIsNTAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwIEg8c3ViPmk8XC9zdWI+XHViMjk0IFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWIxOTJcdWM3NzQgKDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIFx1Yzc3NFx1YmE3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTAgUDxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMyAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsZTsgMjAwMCkgXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIC4uLiwgeDxzdWI+UDxzdWI+aTxcL3N1Yj48XC9zdWI+LCB5PHN1Yj5QPHN1Yj5pPFwvc3ViPjxcL3N1Yj5cdWI4NWMgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIC0zMDAsMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMzAwLDAwMCBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWFjZmMgXHViMGI0XHViODI0XHVhYzAwXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2FsayIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2Ugd291bGQgbGlrZSB0byB2aXNpdCBCb2IuIEhvd2V2ZXIsIHRoZXkgbGl2ZSBpbiBhIGhpbGx5IGxhbmRzY2FwZSwgYW5kIEFsaWNlIGRvZXNuJnJzcXVvO3QgbGlrZSB0byB3YWxrIGluIGhpbGxzLiBTaGUgaGFzIGEgbWFwIG9mIHRoZSBhcmVhLCBzaG93aW5nIHRoZSBoZWlnaHQgY3VydmVzLiBZb3UgaGF2ZSB0byBjYWxjdWxhdGUgdGhlIHRvdGFsIGFsdGl0dWRlIGNsaW1iZWQsIGFuZCB0aGUgdG90YWwgYWx0aXR1ZGUgZGVzY2VuZGVkLCBmb3IgdGhlIHJvdXRlIHdoaWNoIG1pbmltaXplcyB0aGVzZSBudW1iZXJzLiBJdCBkb2VzIG5vdCBtYXR0ZXIgaG93IGZhciBzaGUgaGFzIHRvIHdhbGsgdG8gYWNoaWV2ZSB0aGlzLjxcL3A+XHJcblxyXG48cD5TaW5jZSB5b3UgZG9uJnJzcXVvO3Qga25vdyB3aGF0IHRoZSBsYW5kc2NhcGUgbG9va3MgbGlrZSBpbiBiZXR3ZWVuIHRoZSBoZWlnaHQgY3VydmVzLCB5b3UgY2Fubm90IGtub3cgZXhhY3RseSBob3cgbXVjaCBjbGltYiBhbmQgZGVzY2VudCBzaGUgd2lsbCBhY3R1YWxseSBnZXQgaW4gcHJhY3RpY2UsIGJ1dCB5b3Ugc2hvdWxkIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBwb3NzaWJsZSB1bmRlciBvcHRpbWFsIGNvbmRpdGlvbnMgYmFzZWQgb24gd2hhdCB5b3UgY2FuIGRlZHVjZSBmcm9tIHRoZSBtYXAuPFwvcD5cclxuXHJcbjxwPlRoZSBtYXAgaXMgcmVwcmVzZW50ZWQgYXMgYW4geHkgZ3JpZC4gQWxpY2UgbGl2ZXMgaW4gKDAsIDApLCBhbmQgQm9iIGxpdmVzIGluICgxMDAgMDAwLCAwKS4gVGhlIGhlaWdodCBjdXJ2ZXMgYXJlIHJlcHJlc2VudGVkIGFzIHBvbHlnb25zLCB3aGVyZSBhIHBvbHlnb24gY2Fubm90IGludGVyc2VjdCBpdHNlbGYgb3IgYW5vdGhlciBwb2x5Z29uLiBGdXJ0aGVybW9yZSwgbmVpdGhlciBBbGljZSBub3IgQm9iIGxpdmVzIGV4YWN0bHkgb24gYSBoZWlnaHQgY3VydmUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2FsaygyKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODBweDsgd2lkdGg6MzQ1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+U2Vjb25kIHRlc3QgY2FzZSBmcm9tIHNhbXBsZSBpbnB1dCAoY29tcHJlc3NlZCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIDAgJmxlOyBOICZsZTsgMiA1MDAsIHRoZSBudW1iZXIgb2YgaGVpZ2h0IGN1cnZlcy48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgZm9yIGVhY2ggaGVpZ2h0IGN1cnZlLCB3aXRoIDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIGJlaW5nIHRoZSBoZWlnaHQgb2YgdGhlIGN1cnZlLCAzICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyAyIDAwMCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBwb2x5Z29uLCBhbmQgdGhlIHZlcnRpY2VzIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgLi4uLCB4PHN1Yj5QPHN1Yj5pPFwvc3ViPjxcL3N1Yj4sIHk8c3ViPlA8c3ViPmk8XC9zdWI+PFwvc3ViPiBoYXZpbmcgaW50ZWdyYWwgdmFsdWVzICZtaW51czszMDAgMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMzAwIDAwMC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiAyMDAgMDAwIHBvbHlnb24gdmVydGljZXMgaW4gdG90YWwgaW4gYWxsIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIG51bWJlcnM6IHRoZSB0b3RhbCBhbHRpdHVkZSBjbGltYmVkIGFuZCB0aGUgdG90YWwgYWx0aXR1ZGUgZGVzY2VuZGVkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d