시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB54191732.692%

문제

상근이는 TGN에서 풍선을 잡는 게임을 만들고 있다. 이 게임은 사람들의 동심을 사로잡을 이차원 게임이다. 게임에서 풍선은 하나씩 땅으로 떨어진다. 플레이어는 로봇 자동차를 조종해서 땅으로 떨어지는 풍선을 잡는다. 플레이어는 로봇을 왼쪽이나 오른쪽으로 움직일 수 있고, 그 자리에 멈추어 있게 할 수도 있다. 한 풍선이 땅에 닿을 때 반드시 그 위치에 차량이 있어야 한다. 만약, 차량이 없다면, 풍선은 폭발하게 되고 게임은 끝난다.

게임의 목표는 모든 풍선을 왼족에 있는 집에 보관하는 것이다. 로봇은 풍선을 한 번에 3개까지 운반할 수 있다. 로봇의 이동속도는 운반하는 풍선의 개수에 따라서 달라진다. 로봇이 운반하고 있는 풍선이 k개(k=0, 1, 2, 3)라면, 한 칸 움직이는데 (k+1)초가 걸린다. 플레이어는 로봇이 움직이는 거리가 적을수록 더 높은 점수를 얻게 된다.

상근이는 플레이어가 얻을 수 있는 최고 점수를 계산해보려고 한다. 풍선이 떨어지는 위치와 시간이 주어졌을 때, 모든 풍선을 잡아서 집에 저장하기 위해서 로봇의 이동 회수의 최솟값을 구하는 프로그램을 작성하시오. 로봇 자동차는 집에서 시작한다. 만약, 모든 풍선을 잡을 수 없는 경우에는 잡지못하는 첫 번째 풍선이 무엇인지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 풍선의 개수 n이 주어진다. (0 < n ≤ 40) 다음 n개 줄에는 풍선의 위치 pi와 풍선이 땅에 닿는 시간 ti가 공백으로 구분되어 주어진다. (0 < pi ≤ 100, 0 < ti ≤ 50000) 모든 i < j에 대해서 ti < tj이다. 또, 집의 위치는 0이고, 게임은 시간이 0일 때 시작한다.

로봇 자동차, 집, 풍선의 크기는 매우 작아서 무시할 수 있다. 로봇이 풍선을 잡는데 걸리는 시간과 집에 풍선을 보관하는데 걸리는 시간은 0이다. 또, 자동차는 명령을 받은 후 즉시 움직인다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 다음과 같이 두 가지 중 하나를 출력한다.

만약, 플레이어가 모든 풍선을 잡을 수 있다면, "OK"를 출력하고, 로봇이 풍선을 모두 잡고 보관하는데 필요한 최소 이동 회수를 출력한다. 플레이어가 모든 풍선을 잡을 수 없다면, "NG"를 출력하고, 플레이어가 잡을 수 없는 첫 번째 풍선의 번호를 출력한다.

예제 입력 1

2
10 100
100 270
2
10 100
100 280
3
100 150
10 360
40 450
3
100 150
10 360
40 440
2
100 10
50 200
2
100 100
50 110
1
15 10
4
1 10
2 20
3 100
90 200
0

예제 출력 1

OK 220
OK 200
OK 260
OK 280
NG 1
NG 2
NG 1
OK 188
W3sicHJvYmxlbV9pZCI6IjM4NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0OGRcdWMxMjAgXHVjMjE4XHVjOWQxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgVEdOXHVjNWQwXHVjMTFjIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWM3YTFcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzU4IFx1YjNkOVx1YzJlY1x1Yzc0NCBcdWMwYWNcdWI4NWNcdWM3YTFcdWM3NDQgXHVjNzc0XHVjYzI4XHVjNmQwIFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWQ1NThcdWIwOThcdWM1MjkgXHViNTQ1XHVjNzNjXHViODVjIFx1YjVhOFx1YzViNFx1YzljNFx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1Yjg1Y1x1YmQwNyBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVjODcwXHVjODg1XHVkNTc0XHVjMTFjIFx1YjU0NVx1YzczY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YzdhMVx1YjI5NFx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWM2N2NcdWNhYmRcdWM3NzRcdWIwOTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YmE0OFx1Y2Q5NFx1YzViNCBcdWM3ODhcdWFjOGMgXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDU1YyBcdWQ0OGRcdWMxMjBcdWM3NzQgXHViNTQ1XHVjNWQwIFx1YjJmZlx1Yzc0NCBcdWI1NGMgXHViYzE4XHViNGRjXHVjMmRjIFx1YWRmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjYzI4XHViN2M5XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjYzI4XHViN2M5XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVkNDhkXHVjMTIwXHVjNzQwIFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YWM4YyBcdWI0MThcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iYWxsb29uLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDQ3N3B4OyBoZWlnaHQ6IDI5MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjNjdjXHVjODcxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWM1ZDAgXHViY2Y0XHVhZDAwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViODVjXHViZDA3XHVjNzQwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWQ1NWMgXHViYzg4XHVjNWQwIDNcdWFjMWNcdWFlNGNcdWM5YzAgXHVjNmI0XHViYzE4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc1OCBcdWM3NzRcdWIzZDlcdWMxOGRcdWIzYzRcdWIyOTQgXHVjNmI0XHViYzE4XHVkNTU4XHViMjk0IFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YjJlY1x1Yjc3Y1x1YzljNFx1YjJlNC4gXHViODVjXHViZDA3XHVjNzc0IFx1YzZiNFx1YmMxOFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzc0IGtcdWFjMWMoaz0wLCAxLCAyLCAzKVx1Yjc3Y1x1YmE3NCwgXHVkNTVjIFx1Y2U3OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTRcdWIzNzAgKGsrMSlcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LiBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHViODVjXHViZDA3XHVjNzc0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjODAxXHVjNzQ0XHVjMjE4XHViODVkIFx1YjM1NCBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVhY2UwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ0OGRcdWMxMjBcdWM3NzQgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWM3YTFcdWM1NDRcdWMxMWMgXHVjOWQxXHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViODVjXHViZDA3XHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI4NWNcdWJkMDcgXHVjNzkwXHViM2Q5XHVjYzI4XHViMjk0IFx1YzlkMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjN2ExXHVjOWMwXHViYWJiXHVkNTU4XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNDhkXHVjMTIwXHVjNzc0IFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IG4gJmxlOyA0MCkgXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWM3MDRcdWNlNTggcDxzdWI+aTxcL3N1Yj5cdWM2NDAgXHVkNDhkXHVjMTIwXHVjNzc0IFx1YjU0NVx1YzVkMCBcdWIyZmZcdWIyOTQgXHVjMmRjXHVhYzA0IHQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IHA8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLCAwICZsdDsgdDxzdWI+aTxcL3N1Yj4gJmxlOyA1MDAwMCkgXHViYWE4XHViNGUwIGkgJmx0OyBqXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyB0PHN1Yj5pPFwvc3ViPiAmbHQ7IHQ8c3ViPmo8XC9zdWI+XHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgMFx1Yzc3NFx1YWNlMCwgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc3NCAwXHVjNzdjIFx1YjU0YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHViODVjXHViZDA3IFx1Yzc5MFx1YjNkOVx1Y2MyOCwgXHVjOWQxLCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM3OTFcdWM1NDRcdWMxMWMgXHViYjM0XHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjN2ExXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjOWQxXHVjNWQwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWJjZjRcdWFkMDBcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAwXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1Yzc5MFx1YjNkOVx1Y2MyOFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NDQgXHViYzFiXHVjNzQwIFx1ZDZjNCBcdWM5ODlcdWMyZGMgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWNjXHVjNTdkLCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgJnF1b3Q7T0smcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI4NWNcdWJkMDdcdWM3NzQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM3YTFcdWFjZTAgXHViY2Y0XHVhZDAwXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWJhYThcdWI0ZTAgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtORyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4NjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWxsb29uIENvbGxlY3RpbmciLCJkZXNjcmlwdGlvbiI6IjxwPiZsZHF1bztCYWxsb29ucyBzaG91bGQgYmUgY2FwdHVyZWQgZVx1ZmIwM2NpZW50bHkmcmRxdW87LCB0aGUgZ2FtZSBkZXNpZ25lciBzYXlzLiBIZSBpcyBkZXNpZ25pbmcgYW4gb2xkZmFzaGlvbmVkIGdhbWUgd2l0aCB0d28gZGltZW5zaW9uYWwgZ3JhcGhpY3MuIEluIHRoZSBnYW1lLCBiYWxsb29ucyBmYWxsIG9udG8gdGhlIGdyb3VuZCBvbmUgYWZ0ZXIgYW5vdGhlciwgYW5kIHRoZSBwbGF5ZXIgbWFuaXB1bGF0ZXMgYSByb2JvdCB2ZWhpY2xlIG9uIHRoZSBncm91bmQgdG8gY2FwdHVyZSB0aGUgYmFsbG9vbnMuIFRoZSBwbGF5ZXIgY2FuIGNvbnRyb2wgdGhlIHZlaGljbGUgdG8gbW92ZSBsZWZ0IG9yIHJpZ2h0LCBvciBzaW1wbHkgc3RheS4gV2hlbiBvbmUgb2YgdGhlIGJhbGxvb25zIHJlYWNoZXMgdGhlIGdyb3VuZCwgdGhlIHZlaGljbGUgYW5kIHRoZSBiYWxsb29uIG11c3QgcmVzaWRlIGF0IHRoZSBzYW1lIHBvc2l0aW9uLCBvdGhlcndpc2UgdGhlIGJhbGxvb24gd2lsbCBidXJzdCBhbmQgdGhlIGdhbWUgZW5kcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iYWxsb29uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI5MXB4OyB3aWR0aDo0NzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgQi4xOiBSb2JvdCB2ZWhpY2xlIGFuZCBmYWxsaW5nIGJhbGxvb25zPFwvcD5cclxuXHJcbjxwPlRoZSBnb2FsIG9mIHRoZSBnYW1lIGlzIHRvIHN0b3JlIGFsbCB0aGUgYmFsbG9vbnMgaW50byB0aGUgaG91c2UgYXQgdGhlIGxlZnQgZW5kIG9uIHRoZSBnYW1lIGZpZWxkLiBUaGUgdmVoaWNsZSBjYW4gY2FycnkgYXQgbW9zdCB0aHJlZSBiYWxsb29ucyBhdCBhIHRpbWUsIGJ1dCBpdHMgc3BlZWQgY2hhbmdlcyBhY2NvcmRpbmcgdG8gdGhlIG51bWJlciBvZiB0aGUgY2FycnlpbmcgYmFsbG9vbnMuIFdoZW4gdGhlIHZlaGljbGUgY2FycmllcyBrIGJhbGxvb25zIChrID0gMCwgMSwgMiwgMyksIGl0IHRha2VzIGsrMSB1bml0cyBvZiB0aW1lIHRvIG1vdmUgb25lIHVuaXQgZGlzdGFuY2UuIFRoZSBwbGF5ZXIgd2lsbCBnZXQgaGlnaGVyIHNjb3JlIHdoZW4gdGhlIHRvdGFsIG1vdmluZyBkaXN0YW5jZSBvZiB0aGUgdmVoaWNsZSBpcyBzaG9ydGVyLjxcL3A+XHJcblxyXG48cD5Zb3VyIG1pc3Npb24gaXMgdG8gaGVscCB0aGUgZ2FtZSBkZXNpZ25lciBjaGVjayBnYW1lIGRhdGEgY29uc2lzdGluZyBvZiBhIHNldCBvZiBiYWxsb29ucy4gR2l2ZW4gYSBsYW5kaW5nIHBvc2l0aW9uIChhcyB0aGUgZGlzdGFuY2UgZnJvbSB0aGUgaG91c2UpIGFuZCBhIGxhbmRpbmcgdGltZSBvZiBlYWNoIGJhbGxvb24sIHlvdSBtdXN0IGp1ZGdlIHdoZXRoZXIgYSBwbGF5ZXIgY2FuIGNhcHR1cmUgYWxsIHRoZSBiYWxsb29ucywgYW5kIGFuc3dlciB0aGUgbWluaW11bSBtb3ZpbmcgZGlzdGFuY2UgbmVlZGVkIHRvIGNhcHR1cmUgYW5kIHN0b3JlIGFsbCB0aGUgYmFsbG9vbnMuIFRoZSB2ZWhpY2xlIHN0YXJ0cyBmcm9tIHRoZSBob3VzZS4gSWYgdGhlIHBsYXllciBjYW5ub3QgY2FwdHVyZSBhbGwgdGhlIGJhbGxvb25zLCB5b3UgbXVzdCBpZGVudGlmeSB0aGUgZmlyc3QgYmFsbG9vbiB0aGF0IHRoZSBwbGF5ZXIgY2Fubm90IGNhcHR1cmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBkYXRhc2V0cy4gRWFjaCBkYXRhc2V0IGlzIGZvcm1hdHRlZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48cHJlPlxyXG5uXHJcbnA8c3ViPjE8XC9zdWI+IHQ8c3ViPjE8XC9zdWI+XHJcbi5cclxuLi5cclxucDxzdWI+bjxcL3N1Yj4gdDxzdWI+bjxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIG4sIHdoaWNoIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiBiYWxsb29ucyAoMCAmbHQ7IG4gJmxlOyA0MCkuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBwaSBhbmQgdDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBpICZsZTsgbikgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIHA8c3ViPmk8XC9zdWI+IGFuZCB0PHN1Yj5pPFwvc3ViPiByZXByZXNlbnQgdGhlIHBvc2l0aW9uIGFuZCB0aGUgdGltZSB3aGVuIHRoZSBpLXRoIGJhbGxvb24gcmVhY2hlcyB0aGUgZ3JvdW5kICgwICZsdDsgcDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsIDAgJmx0OyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDUwMDAwKS4gWW91IGNhbiBhc3N1bWUgdDxzdWI+aTxcL3N1Yj4gJmx0OyB0PHN1Yj5qPFwvc3ViPiBmb3IgaSAmbHQ7IGouIFRoZSBwb3NpdGlvbiBvZiB0aGUgaG91c2UgaXMgMCwgYW5kIHRoZSBnYW1lc3RhcnRzIGZyb20gdGhlIHRpbWUgMC48XC9wPlxyXG5cclxuPHA+VGhlIHNpemVzIG9mIHRoZSB2ZWhpY2xlLCB0aGUgaG91c2UsIGFuZCB0aGUgYmFsbG9vbnMgYXJlIHNtYWxsIGVub3VnaCwgYW5kIHNob3VsZCBiZSBpZ25vcmVkLiBUaGUgdmVoaWNsZSBuZWVkcyAwIHRpbWUgZm9yIGNhdGNoaW5nIHRoZSBiYWxsb29ucyBvciBzdG9yaW5nIHRoZW0gaW50byB0aGUgaG91c2UuIFRoZSB2ZWhpY2xlIGNhbiBzdGFydCBtb3ZpbmcgaW1tZWRpYXRlbHkgYWZ0ZXIgdGhlc2Ugb3BlcmF0aW9ucy48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIGEgemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgb25lIHdvcmQgYW5kIG9uZSBpbnRlZ2VyIGluIGEgbGluZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gTm8gZXh0cmEgY2hhcmFjdGVycyBzaG91bGQgb2NjdXIgaW4gdGhlIG91dHB1dC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB0aGUgcGxheWVyIGNhbiBjYXB0dXJlIGFsbCB0aGUgYmFsbG9vbnMsIG91dHB1dCAmbGRxdW87T0smcmRxdW87IGFuZCBhbiBpbnRlZ2VyIHRoYXQgcmVwcmVzZW50cyB0aGUgbWluaW11bSBtb3ZpbmcgZGlzdGFuY2Ugb2YgdGhlIHZlaGljbGUgdG8gY2FwdHVyZSBhbmQgc3RvcmUgYWxsIHRoZSBiYWxsb29ucy48XC9saT5cclxuXHQ8bGk+SWYgaXQgaXMgaW1wb3NzaWJsZSBmb3IgdGhlIHBsYXllciB0byBjYXB0dXJlIGFsbCB0aGUgYmFsbG9vbnMsIG91dHB1dCAmbGRxdW87TkcmcmRxdW87IGFuZCBhbiBpbnRlZ2VyIGsgc3VjaCB0aGF0IHRoZSBrLXRoIGJhbGxvb24gaW4gdGhlIGRhdGFzZXQgaXMgdGhlIFx1ZmIwMXJzdCBiYWxsb29uIHRoYXQgdGhlIHBsYXllciBjYW5ub3QgY2FwdHVyZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2010 in Tokyo B번