시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB262778151531.556%

문제

아래와 같이 M행 N열 격자 그리드로 설계된 운전 면허 시험장에서 운전 면허 시험을 치르려 한다.

시험의 규칙은 세 가지이다.

  • 규칙 1 : 응시자는 가장 왼쪽 위의 s지점에서 시작하여 동쪽(오른쪽), 남쪽(아래쪽)으로만 차를 몰아 가장 오른쪽 아래의 최종 도착지 t에 도착해야 한다.
  • 규칙 2 : 차를 아래로 모는 시간과 오른쪽으로 모는 시간은 격자 한 칸당 L로 동일해야 한다. (L은 시험 시작 전에 주어지는 상수이다). 또한, 방향을 바꾸는 데 걸리는 시간은 항상 1이다. 단, 시작점 s에서는 오른쪽이나 아래 방향 중 원하는 방향을 골라 출발할 수 있다. 즉, 시작점에서는 방향을 바꾸는 데 시간이 들지 않는다.
  • 규칙 3 : 시험을 시작하기 전 G만큼의 연료를 주입한다.(G는 시험 시작 전에 결정된다). 응시자는 G 이하의 연료를 사용한다는 조건 하에 가장 빨리 도착할 수 있는 방법으로 t에 도착해야 한다.

규칙 2를 만족하기 위해, 응시자는 도로의 상태에 따라 알맞은 방법으로 차를 몰아야 한다. 따라서, 각 도로의 상태에 따라 소모되는 연료량이 다르다. 이에 따라 응시자는 G 이하의 연료만을 사용하여 t에 도착하는 경로를 찾아야 한다.

위에 예시로 주어진 4*6 그리드에서 각 도로에 쓰여진 정수가 그 도로를 시간 L동안 주행하는 데에 드는 연료량이다. 방향을 바꿀 때는 연료가 사용되지 않는다.

위의 그림은 G=19이며 L=10일 때 가능한 두 가지 경로를 표시한 것이다.

왼쪽의 경로는 17의 연료를 사용하여 83의 시간만에 아래에 도달하는 경로이다. 이 경로에는 8번의 직선 주행과 3번의 방향 변경이 있었다. 오른쪽의 경로는 연료를 덜 쓰는 경로이지만(16), 주행 시간의 합이 85로 더 오래 걸린다. 사실 위의 경로 외에도 19 이하의 연료 사용으로 83의 시간으로 도달할 수 있는 경로가 몇 가지 더 있다. 하지만, 19 이하의 연료를 사용하여 83보다 더 빠른 시간 내에 t에 도착하는 방법은 존재하지 않는다.

이제 주행 시험이 시작된다. 그리드의 상태와 G, L이 주어질 때, 가장 빠르게 목적지 t에 도달하는 시간은 얼마일까?

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 네 개의 정수 M, N, L, G로 이루어져 있으며 M은 그리드의 행 수, N은 그리드의 열 수이다. L은 문제에서 설명한 한 격자를 직선 주행하는 데 걸리는 시간이며 G는 연료량이다. (2 ≤ M, N ≤ 100), (1 ≤ L ≤ 10), (1 ≤ G ≤ 1,000,000). 이어서 M줄에 걸쳐 N-1개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 가로 경로를 주행할 때 드는 연료량이다. 그 이후 M-1줄에 걸쳐 N개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 세로 경로를 주행할 때 드는 연료량이다.

모든 단위 경로에서 소모되는 연료량은 1 이상 1000 이하의 값을 갖는다.

출력

만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다.

예제 입력 1

3
4 6 10 19
4 3 6 7 9
3 1 2 7 5
2 2 6 1 9
5 3 4 3 2
1 5 4 4 4 2
6 1 1 3 1 7
2 2 3 2 3 5
3 4 5 10
4 5 6
2 3 1
5 7 8
1 8 6 7
4 6 9 1
3 3 10 9
2 2
2 2
2 2
3 3 3
3 3 3

예제 출력 1

83
27
-1
W3sicHJvYmxlbV9pZCI6IjEwMjUxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmI0XHVjODA0IFx1YmE3NFx1ZDVjOCBcdWMyZGNcdWQ1ZDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgTVx1ZDU4OSBOXHVjNWY0IFx1YWNhOVx1Yzc5MCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI4NWMgXHVjMTI0XHVhY2M0XHViNDFjIFx1YzZiNFx1YzgwNCBcdWJhNzRcdWQ1YzggXHVjMmRjXHVkNWQ4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YzZiNFx1YzgwNCBcdWJhNzRcdWQ1YzggXHVjMmRjXHVkNWQ4XHVjNzQ0IFx1Y2U1OFx1Yjk3NFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgc3JjPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvdXBsb2FkXC9pbWFnZXMyXC9kcml2aW5nMSgxKS5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNWQ4XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWMxMzggXHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxzdHJvbmc+XHVhZGRjXHVjZTU5IDE8XC9zdHJvbmc+IDogXHVjNzUxXHVjMmRjXHVjNzkwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjNzU4IHNcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YjNkOVx1Y2FiZChcdWM2MjRcdWI5NzhcdWNhYmQpLCBcdWIwYThcdWNhYmQoXHVjNTQ0XHViNzk4XHVjYWJkKVx1YzczY1x1Yjg1Y1x1YjljYyBcdWNjMjhcdWI5N2MgXHViYWIwXHVjNTQ0IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWIzYzRcdWNjMjlcdWM5YzAgdFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlx1YWRkY1x1Y2U1OSAyPFwvc3Ryb25nPiA6IFx1Y2MyOFx1Yjk3YyBcdWM1NDRcdWI3OThcdWI4NWMgXHViYWE4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHViYWE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWFjYTlcdWM3OTAgXHVkNTVjIFx1Y2U3OFx1YjJmOSBMXHViODVjIFx1YjNkOVx1Yzc3Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIChMXHVjNzQwIFx1YzJkY1x1ZDVkOCBcdWMyZGNcdWM3OTEgXHVjODA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMwYzFcdWMyMThcdWM3NzRcdWIyZTQpLiBcdWI2MTBcdWQ1NWMsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMTRcdWFmYjhcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVkNTZkXHVjMGMxIDFcdWM3NzRcdWIyZTQuIFx1YjJlOCwgXHVjMmRjXHVjNzkxXHVjODEwIHNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHViMDk4IFx1YzU0NFx1Yjc5OCBcdWJjMjlcdWQ1YTUgXHVjOTExIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVhY2U4XHViNzdjIFx1Y2Q5Y1x1YmMxY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViYzE0XHVhZmI4XHViMjk0IFx1YjM3MCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViNGU0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5cdWFkZGNcdWNlNTkgMzxcL3N0cm9uZz4gOiBcdWMyZGNcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNCBHXHViOWNjXHVkMDdjXHVjNzU4IFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWM4ZmNcdWM3ODVcdWQ1NWNcdWIyZTQuKEdcdWIyOTQgXHVjMmRjXHVkNWQ4IFx1YzJkY1x1Yzc5MSBcdWM4MDRcdWM1ZDAgXHVhY2IwXHVjODE1XHViNDFjXHViMmU0KS4gXHVjNzUxXHVjMmRjXHVjNzkwXHViMjk0IEcgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjODcwXHVhYzc0IFx1ZDU1OFx1YzVkMCBcdWFjMDBcdWM3YTUgXHViZTY4XHViOWFjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyB0XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhZGRjXHVjZTU5IDJcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjNzUxXHVjMmRjXHVjNzkwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzU0Y1x1YjlkZVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjYzI4XHViOTdjIFx1YmFiMFx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzE4Y1x1YmFhOFx1YjQxOFx1YjI5NCBcdWM1ZjBcdWI4Y2NcdWI3YzlcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0LiBcdWM3NzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1Yzc1MVx1YzJkY1x1Yzc5MFx1YjI5NCBHIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1ZjBcdWI4Y2NcdWI5Y2NcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIHRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM1ZDAgXHVjNjA4XHVjMmRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCA0KjYgXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM1ZDAgXHVjNGYwXHVjNWVjXHVjOWM0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1YzJkY1x1YWMwNCBMXHViM2Q5XHVjNTQ4IFx1YzhmY1x1ZDU4OVx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHViNGRjXHViMjk0IFx1YzVmMFx1YjhjY1x1YjdjOVx1Yzc3NFx1YjJlNC4gXHViYzI5XHVkNWE1XHVjNzQ0IFx1YmMxNFx1YWZjMCBcdWI1NGNcdWIyOTQgXHVjNWYwXHViOGNjXHVhYzAwIFx1YzBhY1x1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgc3JjPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvdXBsb2FkXC9pbWFnZXMyXC9kcml2aW5nMigxKS5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBHPTE5XHVjNzc0XHViYTcwIEw9MTBcdWM3N2MgXHViNTRjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWQ0NWNcdWMyZGNcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmRcdWM3NTggXHVhY2JkXHViODVjXHViMjk0IDE3XHVjNzU4IFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgODNcdWM3NTggXHVjMmRjXHVhYzA0XHViOWNjXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2JkXHViODVjXHVjNWQwXHViMjk0IDhcdWJjODhcdWM3NTggXHVjOWMxXHVjMTIwIFx1YzhmY1x1ZDU4OVx1YWNmYyAzXHViYzg4XHVjNzU4IFx1YmMyOVx1ZDVhNSBcdWJjYzBcdWFjYmRcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NTggXHVhY2JkXHViODVjXHViMjk0IFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWIzNWMgXHVjNGYwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YzljMFx1YjljYygxNiksIFx1YzhmY1x1ZDU4OSBcdWMyZGNcdWFjMDRcdWM3NTggXHVkNTY5XHVjNzc0IDg1XHViODVjIFx1YjM1NCBcdWM2MjRcdWI3OTggXHVhYzc4XHViOWIwXHViMmU0LiBcdWMwYWNcdWMyZTQgXHVjNzA0XHVjNzU4IFx1YWNiZFx1Yjg1YyBcdWM2NzhcdWM1ZDBcdWIzYzQgMTkgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzVmMFx1YjhjYyBcdWMwYWNcdWM2YTlcdWM3M2NcdWI4NWMgODNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWJhODcgXHVhYzAwXHVjOWMwIFx1YjM1NCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgMTkgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzVmMFx1YjhjY1x1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgODNcdWJjZjRcdWIyZTQgXHViMzU0IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDQgXHViMGI0XHVjNWQwIHRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjOGZjXHVkNTg5IFx1YzJkY1x1ZDVkOFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWM2NDAgRywgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc0XHVhYzhjIFx1YmFhOVx1YzgwMVx1YzljMCB0XHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTSwgTiwgTCwgR1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPk1cdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1ZDU4OSBcdWMyMTgsIE5cdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1YzVmNCBcdWMyMThcdWM3NzRcdWIyZTQuIExcdWM3NDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWQ1NWMgXHVhY2E5XHVjNzkwXHViOTdjIFx1YzljMVx1YzEyMCBcdWM4ZmNcdWQ1ODlcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWJhNzAgR1x1YjI5NCBcdWM1ZjBcdWI4Y2NcdWI3YzlcdWM3NzRcdWIyZTQuICgyICZsZTsgTSwgTiAmbGU7IDEwMCksICgxICZsZTsgTCAmbGU7IDEwKSwgKDEgJmxlOyBHICZsZTsgMSwwMDAsMDAwKS4mbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWM3NzRcdWM1YjRcdWMxMWMgTVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgTi0xXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHVjNWQwXHVjMTFjIFx1YjMwMFx1Yzc1MVx1YjQxOFx1YjI5NCBcdWFjMDBcdWI4NWMgXHVhY2JkXHViODVjXHViOTdjIFx1YzhmY1x1ZDU4OVx1ZDU2MCBcdWI1NGMgXHViNGRjXHViMjk0IFx1YzVmMFx1YjhjY1x1YjdjOVx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFkZjggXHVjNzc0XHVkNmM0IE0tMVx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YzExYyBcdWIzMDBcdWM3NTFcdWI0MThcdWIyOTQgXHVjMTM4XHViODVjIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM4ZmNcdWQ1ODlcdWQ1NjAgXHViNTRjIFx1YjRkY1x1YjI5NCBcdWM1ZjBcdWI4Y2NcdWI3YzlcdWM3NzRcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjJlOFx1YzcwNCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVjMThjXHViYWE4XHViNDE4XHViMjk0IFx1YzVmMFx1YjhjY1x1YjdjOVx1Yzc0MCAxIFx1Yzc3NFx1YzBjMSAxMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1Yzc3YyBHIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1ZjBcdWI4Y2NcdWI3YzlcdWM3M2NcdWI4NWMgc1x1YzVkMFx1YzExYyB0XHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHViZTY4XHViOWFjIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDI1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRyaXZpbmcgTGljZW5zZSIsImRlc2NyaXB0aW9uIjoiPHA+VGFraW5nIGEgZHJpdmluZyB0ZXN0IG11c3QgbWFrZSBwZW9wbGUgbmVydm91cyBpbiBhbG1vc3QgZXZlcnkgY2l0eSBpbiB0aGUgd29ybGQuIFBlb3BsZSBpbiBHcmlkIGNpdHkgaW4gd2hpY2ggcm9hZCBuZXR3b3JrIGxvb2tzIGxpa2UgYSBncmlkIHNob3VsZCBwYXNzIGFuIGludGVyZXN0aW5nIGRyaXZpbmcgdGVzdCBpbiBvcmRlciB0byBvYnRhaW4gYSBkcml2ZXImcnNxdW87cyBsaWNlbnNlLiBJbmZvcm1hdGlvbiBvbiBhbiBNICZ0aW1lczsgTiBncmlkLXNoYXBlZCByb2FkIG5ldHdvcmsgaXMgZ2l2ZW4gdG8gdGhlIGFwcGxpY2FudCBiZWZvcmUgaGUgdGFrZXMgdGhlIHRlc3QgaW4gdGhlIGNpdHkuIFVzaW5nIHRoZSBnaXZlbiBpbmZvcm1hdGlvbiwgaGUgaGFzIHRvIGNvbXBseSB3aXRoIDMgcnVsZXMsIGRlc2NyaWJlZCBiZWxvdywgdG8gcGFzcyB0aGUgdGVzdC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kcml2aW5nMSgxKS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjA1cHg7IHdpZHRoOjI4NnB4XCIgXC8+UnVsZSAxPFwvc3Ryb25nPjogSGUgbXVzdCBkcml2ZSBhIGNhciBlYXN0d2FyZCBvciBkb3dud2FyZCBmcm9tIHRoZSBzdGFydGluZyBwb2ludCBzLCBsb2NhdGVkIGF0IHVwcGVyLWxlZnQgY29ybmVyIG9mIHRoZSBncmlkLCB0byB0aGUgZW5kaW5nIHBvaW50IHQsIGxvY2F0ZWQgYXQgbG93ZXItcmlnaHQgY29ybmVyIG9mIHRoZSBncmlkLiZuYnNwOzxcL3A+XHJcblxyXG48cD48c3Ryb25nPlJ1bGUgMjxcL3N0cm9uZz46IFRoZSBkcml2aW5nIHRpbWUgZm9yIGVhY2ggc2VnbWVudCAoZWl0aGVyIHZlcnRpY2FsIG9yIGhvcml6b250YWwpIG9mIHRoZSBncmlkIG11c3QgYmUgZXhhY3RseSBMICh3aGljaCBpcyBnaXZlbiBiZWZvcmUgdGFraW5nIHRoZSB0ZXN0KSBhbmQgdGhlIHR1cm5pbmcgdGltZSB0byBjaGFuZ2UgZGlyZWN0aW9uIG11c3QgYmUgZXhhY3RseSAxLiBObyB0dXJuaW5nIHRpbWUgaXMgYXNzdW1lZCBhdCB0aGUgc3RhcnRpbmcgcG9pbnQgcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5SdWxlIDM8XC9zdHJvbmc+OiBVc2luZyBhbiBhbW91bnQgb2YgZnVlbCwgc2F5IEcsIGdpdmVuIGJlZm9yZSB0YWtpbmcgdGhlIHRlc3QsIGhlIGhhcyB0byByZWFjaCB0IGFzIHNvb24gYXMgcG9zc2libGUgd2l0aG91dCBjb25zdW1pbmcgYWRkaXRpb25hbCBmdWVsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgaGUgaGFzIHRvIGNvbnRyb2wgdGhlIHNwZWVkIG9mIHRoZSBjYXIgY29uc2lkZXJpbmcgdGhlIHJvYWQgY29uZGl0aW9uIHRvIGNvbXBseSB3aXRoIHRoZSBydWxlIDIuIFNvLCB0aGUgYW1vdW50IG9mIGZ1ZWwgY29uc3VtZWQgdG8gcGFzcyBlYWNoIHNlZ21lbnQgY291bGQgYmUgZGlmZmVyZW50LiBBbHNvIG5vdGUgdGhhdCBoZSBoYXMgdG8gZmluZCBhIGZhc3Rlc3Qgcm91dGUgYW1vbmcgc2V2ZXJhbCBwb3NzaWJsZSByb3V0ZXMgYWxvbmcgd2hpY2ggaGUgY2FuIGRyaXZlIHVzaW5nIGFzIG11Y2ggZnVlbCBhcyBHLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaWcuIDEgc2hvd3MgYSA0ICZ0aW1lczsgNiBncmlkLXNoYXBlZCByb2FkIG5ldHdvcmssIHdoaWNoIGhhcyA0IGhvcml6b250YWwgc3RyZWV0cyBhbmQgNiB2ZXJ0aWNhbCBzdHJlZXRzLiBOdW1iZXJzIHNob3duIGZvciBlYWNoIHNlZ21lbnQgb2YgdGhlIGdyaWQgZGVub3RlIHRoZSByZXF1aXJlZCBhbW91bnQgb2YgZnVlbCB0byBwYXNzIGl0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZHJpdmluZzIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjIzcHg7IHdpZHRoOjU5MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlN1cHBvc2UgYSByb2FkIG5ldHdvcmsgYXMgc2hvd24gaW4gRmlnLiAxIGFuZCBHID0gMTkgYW5kIEwgPSAxMCBhcmUgZ2l2ZW4gYXMgaW5wdXQuIEZpZy4gMiBzaG93cyB0d28gcG9zc2libGUgcm91dGVzLiBUaGUgcm91dGUgc2hvd24gaW4gdGhlIGxlZnQgZmlndXJlIGNvbnN1bWVzIGZ1ZWwgYXMgbXVjaCBhcyAxNyBhbmQgaXQgdGFrZXMgZHJpdmluZyB0aW1lIDgzIHNpbmNlIGl0IHBhc3NlcyA4IGdyaWQgc2VnbWVudHMgYW5kIGNoYW5nZXMgZGlyZWN0aW9uIDMgdGltZXMuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGUgcm91dGUgc2hvd24gaW4gdGhlIHJpZ2h0IGZpZ3VyZSBjb25zdW1lcyBhIGJpdCBsZXNzIGZ1ZWwgYnV0IGl0IHRha2VzIGRyaXZpbmcgdGltZSA4NS4gTm90ZSB0aGF0IHRoZXJlIGFyZSBzb21lIG90aGVyIHJvdXRlcyBhbG9uZyB3aGljaCBoZSBjYW4gZHJpdmUgd2l0aCBmdWVsIDE5IHdpdGhpbiB0aW1lIDgzLiBIb3dldmVyLCB0aGVyZSBpcyBubyByb3V0ZSBhbG9uZyB3aGljaCBoZSBjYW4gZHJpdmUgZmFzdGVyIHdpdGggZnVlbCAxOS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byBtYWtlIGEgcHJvZ3JhbSB3aGljaCBoZWxwcyB0byBmaW5kIGEgcm91dGUgdG8gcGFzcyB0aGUgZHJpdmluZyB0ZXN0IGluIEdyaWQgY2l0eS4gWW91IGNhbiBhc3N1bWUgdGhhdCBnaXZlbiBhIGdyaWQsIHRoZSBzdGFydGluZyBwb2ludCBsb2NhdGVzIGF0IHVwcGVyLWxlZnQgY29ybmVyIGFuZCB0aGUgZW5kaW5nIHBvaW50IGF0IGxvd2VyLXJpZ2h0IGNvcm5lciBhbmQgdGhhdCBubyBmdWVsIGlzIGNvbnN1bWVkIGZvciB0dXJuaW5nIGRpcmVjdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggNCBpbnRlZ2VyczogTSwgTiwgTCwgYW5kIEcsIHdoZXJlIE0gYW5kIE4gKDIgJmxlOyBNLCBOICZsZTsgMTAwKSBkZW5vdGUgdGhlIGRpbWVuc2lvbiBvZiB0aGUgZ3JpZCwgTCAoMSAmbGU7IEwgJmxlOyAxMCkgdGhlIGRyaXZpbmcgdGltZSB0byBwYXNzIGVhY2ggZ3JpZCBzZWdtZW50LCBhbmQgRyAoMSAmbGU7IEcgJmxlOyAxLCAwMDAsIDAwMCkgdGhlIGFtb3VudCBvZiBmdWVsIGdpdmVuIGJlZm9yZSB0ZXN0aW5nLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBOIC0gMSBpbnRlZ2VycywgZWFjaCBvZiB3aGljaCBkZW5vdGVzIHRoZSBhbW91bnQgb2YgZnVlbCBjb25zdW1lZCB0byBwYXNzIHRoZSBjb3JyZXNwb25kaW5nIGhvcml6b250YWwgc2VnbWVudCBvZiB0aGUgZ3JpZC4gQW5vdGhlciBNIC0gMSBsaW5lcyBmb2xsb3cuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIC0gMSBsaW5lcyBjb250YWlucyBOIGludGVnZXJzLCBlYWNoIG9mIHdoaWNoIGRlbm90ZXMgdGhlIGFtb3VudCBvZiBmdWVsIGNvbnN1bWVkIHRvIHBhc3MgdGhlIGNvcnJlc3BvbmRpbmcgdmVydGljYWwgc2VnbWVudCBvZiB0aGUgZ3JpZC4gRWFjaCBpbnRlZ2VyIHVzZWQgZm9yIHRoZSBhbW91bnQgb2YgZnVlbCB0byBwYXNzIGVhY2ggY29ycmVzcG9pbmcgc2VnbWVudCBvZiB0aGUgZ3JpZCBpcyB3aXRoaW4gMSBhbmQgMSwwMDAgaW5jbHVzaXZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGwgdGhlIGludGVnZXJzIHNob3duIGluIGEgc2FtZSBsaW5lIGFyZSBzZXBhcmF0ZWQgYnkgYSBibGFuay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIHNob3cgdGhlIHRvdGFsIGVsYXBzZWQgdGltZSBhbG9uZyB0aGUgZmFzdGVzdCByb3V0ZS4gSWYgaXQgaXMgaW1wb3NzaWJsZSB0byBkcml2ZSBmcm9tIHMgdG8gdCBhbG9uZyBhbnkgcm91dGUgd2l0aCBnaXZlbiBhbW91bnQgb2YgZnVlbCBHLCBwcmludCAtMS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2014 B번