시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 346 112 75 36.585%

문제

지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 있는 길에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다.

상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했다.

이미 고둘라 창지즈 영사우드는 상그니 아라비아로 돌아갔다. 하지만 상근이는 고둘라가 한국에 왔었을 때, 어떤 길로 이동을 했어야 배달을 빠르게 할 수 있었는지 알아보려고 한다. 상근이는 고둘라가 이동한 경로를 알고 있다.

도시는 여러 개의 교차로와 교차로를 서로 연결하는 양방향 도로로 모델링할 수 있다. 상근이는 각 도로를 이동하는데 걸리는 시간을 알고 있다. 고둘라가 그 도로를 이동하는데 걸리는 시간도 같다.

예를 들어, 고둘라가 10분이 되던 때에 어떤 도로에 도착했고, 그 도로를 통과하는데 걸리는 시간이 5라고 하자. 그럼 이 도로는 10, 11, 12, 13, 14분에는 진입할 수 없다. 상근이는 9분 이전, 15분 이후에 이 도로에 진입할 수 있다.

상근이가 배달을 하는데 걸리는 시간의 최소값을 구하는 프로그램을 작성하시오. 상근이는 고둘라가 출발하고 K분이 지난 후에 배달을 시작한다.

입력

첫째 줄에 교차로의 수 N과 도로의 수 M이 주어진다. 교차로는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10,000)

둘째 줄에는 네 정수 A, B, K, G가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000) A는 상근이가 배달을 시작하는 교차로, B는 상근이가 배달을 마치는 교차로이다. K는 고둘라가 출발한 시간과 상근이가 출발한 시간의 차이, G는 고둘라가 방문하는 교차로의 개수이다.

셋째 줄에는 G개의 정수가 주어진다.이 정수는 고둘라가 방문하는 교차로이다. 인접한 교차로 사이의 거리를 고둘라가 이동하는 것이다. 항상 교차로는 존재하며, 각 도로를 최대 한 번만 이동한다.

넷째 줄부터 M개 줄에는 도로의 정보를 나타내는 세 정수 A, B, L이 주어진다. 교차로 A와 B를 연결하는 도로를 이동하는데 L분이 걸린다는 뜻이다. L은 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

첫째 줄에 상근이가 배달을 마치는데 필요한 가장 빠른 시간을 출력한다.

예제 입력 1

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15

예제 출력 1

21
W3sicHJvYmxlbV9pZCI6IjI5ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmRcdWM2NTVcdWM3NTggXHViYzI5XHViYjM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIwOWNcdWM4ZmNcdWM1ZDAgXHVjMGMxXHVhZGY4XHViMmM4IFx1YzU0NFx1Yjc3Y1x1YmU0NFx1YzU0NFx1Yzc1OCBcdWFkNmRcdWM2NTUgXHVhY2UwXHViNDU4XHViNzdjIFx1Y2MzZFx1YzljMFx1Yzk4OCBcdWM2MDFcdWMwYWNcdWM2YjBcdWI0ZGNcdWFjMDAgXHVkNTVjXHVhZDZkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1YjJlNC4gXHVhY2UwXHViNDU4XHViNzdjXHViMjk0IFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWNiZFx1Y2MzMFx1Yzc0MCBcdWFkZjhcdWFjMDAgXHVkMGMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWI3YzlcdWM3NzQgXHVhZTM4XHVjNWQwIFx1YzljNFx1Yzc4NVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhZTM4XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWNjMjhcdWI3YzlcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjJjIFx1YzIxOCBcdWM1YzZcdWFjOGMgXHVkMWI1XHVjODFjXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkZjhcdWFjMDAgXHVjOWM0XHVjNzg1XHVkNTU4XHVhZTMwIFx1YzgwNFx1YmQ4MFx1ZDEzMCBcdWFlMzhcdWM1ZDAgXHVjNzg4XHViMzU4IFx1Y2MyOFx1YjdjOVx1Yzc0MCBcdWFjYzRcdWMxOGQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2MjRcdWQxYTBcdWJjMTRcdWM3NzQgXHVjMThjXHViMTQ0IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1Yzc1OCBcdWI0YTRcdWI5N2MgXHVjNzc0XHVjNWI0IFx1YWRmY1x1Y2M5OFx1YzVkMFx1YzExYyBcdWQ1M2NcdWM3OTBcdWI5N2MgXHVkMmI4XHViN2VkXHVjNzNjXHViODVjIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFkNTBcdWQxYjUgXHVkMWI1XHVjODFjIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVjODE1XHVjMmRjXHVjNWQwIFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NzRcdWMxMWMgXHVjOWU0XHViOWI0XHViZWQ0XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWJiZjggXHVhY2UwXHViNDU4XHViNzdjIFx1Y2MzZFx1YzljMFx1Yzk4OCBcdWM2MDFcdWMwYWNcdWM2YjBcdWI0ZGNcdWIyOTQgXHVjMGMxXHVhZGY4XHViMmM4IFx1YzU0NFx1Yjc3Y1x1YmU0NFx1YzU0NFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMTRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1ZDU1Y1x1YWQ2ZFx1YzVkMCBcdWM2NTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHVhZTM4XHViODVjIFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1ODhcdWM1YjRcdWM1N2MgXHViYzMwXHViMmVjXHVjNzQ0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHViMjk0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVhZDUwXHVjYzI4XHViODVjXHVjNjQwIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yjk3YyBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWI4NWMgXHViYWE4XHViMzc4XHViOWMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHViM2M0XHViODVjXHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHViM2M0IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIDEwXHViZDg0XHVjNzc0IFx1YjQxOFx1YjM1OCBcdWI1NGNcdWM1ZDAgXHVjNWI0XHViNWE0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWFjZTAsIFx1YWRmOCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgNVx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjdmYyBcdWM3NzQgXHViM2M0XHViODVjXHViMjk0IDEwLCAxMSwgMTIsIDEzLCAxNFx1YmQ4NFx1YzVkMFx1YjI5NCBcdWM5YzRcdWM3ODVcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDlcdWJkODQgXHVjNzc0XHVjODA0LCAxNVx1YmQ4NCBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM5YzRcdWM3ODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjZTBcdWI0NThcdWI3N2NcdWFjMDAgXHVjZDljXHViYzFjXHVkNTU4XHVhY2UwIEtcdWJkODRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZDUwXHVjYzI4XHViODVjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMCwgMiAmbGU7IE0gJmxlOyAxMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTI0IFx1YzgxNVx1YzIxOCBBLCBCLCBLLCBHXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBLCBCICZsZTsgTiwgMCAmbGU7IEsgJmxlOyAxMDAwLCAwICZsZTsgRyAmbGU7IDEwMDApIEFcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhZDUwXHVjYzI4XHViODVjLCBCXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHViOWM4XHVjZTU4XHViMjk0IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gS1x1YjI5NCBcdWFjZTBcdWI0NThcdWI3N2NcdWFjMDAgXHVjZDljXHViYzFjXHVkNTVjIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjZDljXHViYzFjXHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWNjMjhcdWM3NzQsIEdcdWIyOTQgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEdcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cdWM3NzQgXHVjODE1XHVjMjE4XHViMjk0IFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHVhZDUwXHVjYzI4XHViODVjXHVjNzc0XHViMmU0LiBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhZDUwXHVjYzI4XHViODVjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWFkNTBcdWNjMjhcdWI4NWNcdWIyOTQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwLCBcdWFjMDEgXHViM2M0XHViODVjXHViOTdjIFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTM3XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IEEsIEIsIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkNTBcdWNjMjhcdWI4NWMgQVx1YzY0MCBCXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIExcdWJkODRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gTFx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHRU9SR0UiLCJkZXNjcmlwdGlvbiI6IjxwPkxhc3Qgd2VlayBNaXN0ZXIgR2VvcmdlIHZpc2l0ZWQgQ3JvYXRpYS4gU2luY2UgTWlzdGVyIEdlb3JnZSBpcyBhIHZlcnkgaW1wb3J0YW50IHBlcnNvbiwgd2hpbGUgaGUgd2FzIGluIGEgc3RyZWV0LCB0aGUgcG9saWNlIGRpc2FsbG93ZWQgZW50cnkgdG8gdGhhdCBzdHJlZXQsIGJ1dCB2ZWhpY2xlcyB0aGF0IGVudGVyZWQgdGhlIHN0cmVldCBiZWZvcmUgTWlzdGVyIEdlb3JnZSBjb3VsZCBjb250aW51ZSBkcml2aW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGlsZSBNaXN0ZXIgR2VvcmdlIHdhcyB2aXNpdGluZywgTHVrYSBkcm92ZSBoaXMgdHJ1Y2sgYXJvdW5kIHRvd24uIEJ1dCBiZWNhdXNlIG9mIHNvbWUgb2YgdGhlIHN0cmVldHMgYmVpbmcgY2xvc2VkIG9mZiwgaGUgY291bGRuJiMzOTt0IG1ha2UgaGlzIGRlbGl2ZXJ5IGluIHRpbWUgYW5kIGFsbW9zdCBsb3N0IGhpcyBqb2IuIEFsdGhvdWdoIGl0IGlzIGxhdGUgbm93LCBoZSBpcyB3b25kZXJpbmcgaG93IGhlIGNvdWxkIGhhdmUgcGxhbm5lZCBoaXMgZGVsaXZlcnkgYmV0dGVyIGkuZS4gd2hhdCB3b3VsZCBoYXZlIGJlZW4gdGhlIGxlYXN0IHRpbWUgbmVlZGVkIHRvIG1ha2UgaGlzIGRlbGl2ZXJ5IHdoaWxlIE1pc3RlciBHZW9yZ2Ugd2FzIHZpc2l0aW5nLiBIZSBrbm93cyB0aGUgcm91dGUgbWlzdGVyIEdlb3JnZSB0b29rLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2l0eSBpcyBtb2RlbGVkIHdpdGggaW50ZXJzZWN0aW9ucyBhbmQgdHdvLXdheSBzdHJlZXRzIGNvbm5lY3RpbmcgdGhlbS4gRm9yIGVhY2ggc3RyZWV0LCBMdWthIGtub3dzIGhvdyBtdWNoIHRpbWUgaGUgbmVlZHMgdG8gdHJhdmVyc2UgaXQgKG1pc3RlciBHZW9yZ2UgbmVlZHMgdGhlIHNhbWUgYW1vdW50IG9mIHRpbWUpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgTWlzdGVyIEdlb3JnZSBzdGFydHMgdHJhdmVyc2luZyBhIHN0cmVldCBkdXJpbmcgbWludXRlIDEwIGFuZCBuZWVkcyA1IG1pbnV0ZXMgdG8gZXhpdCBpdCwgdGhpcyBzdHJlZXQgd2lsbCBiZSBibG9ja2VkIGR1cmluZyBtaW51dGVzIDEwLCAxMSwgMTIsIDEzIGFuZCAxNC4gTHVrYSBjYW4gZW50ZXIgdGhlIHN0cmVldCBkdXJpbmcgbWludXRlcyA5IGFuZCBlYXJsaWVyLCBvciAxNSBhbmQgbGF0ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIGxlYXN0IGFtb3VudCBvZiB0aW1lIEx1a2EgbmVlZHMgdG8gbWFrZSBoaXMgZGVsaXZlcnksIGlmIGhlIHN0YXJ0cyBkcml2aW5nIEsgbWludXRlcyBhZnRlciB0aGUgYXJyaXZhbCBvZiBNaXN0ZXIgR2VvcmdlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gKDIgJmxlOyBOICZsZTsgMTAwMCwgMiAmbGU7IE0gJmxlOyAxMCAwMDApLCB0aGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgYW5kIHRoZSBudW1iZXIgb2Ygc3RyZWV0cy4gVGhlIGludGVyc2VjdGlvbnMgYXJlIG51bWJlcmVkIDEgdG8gTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGZvdXIgaW50ZWdlcnMgQSwgQiwgSyBhbmQgRyAoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgSyAmbGU7IDEwMDAsIDAgJmxlOyBHICZsZTsgMTAwMCkuIFRoZXNlIGFyZSwgaW4gb3JkZXI6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGludGVyc2VjdGlvbiB3aGVyZSBMdWthIHN0YXJ0czsmbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIGludGVyc2VjdGlvbiBMdWthIG11c3QgZ2V0IHRvOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgZGlmZmVyZW5jZSBpbiBzdGFydGluZyB0aW1lcyBiZXR3ZWVuIG1pc3RlciBHZW9yZ2UgYW5kIEx1a2EgKEx1a2Egc3RhcnRzIGF0IGludGVyc2VjdGlvbiBBIGV4YWN0bHkgSyBtaW51dGVzIGFmdGVyIG1pc3RlciBHZW9yZ2Ugc3RhcnRzIGhpcyByb3V0ZSk7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgb2YgaW50ZXJzZWN0aW9ucyBvbiBNaXN0ZXIgR2VvcmdlJiMzOTtzIHJvdXRlLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIEcgaW50ZWdlcnMsIHRoZSBsYWJlbHMgb2YgaW50ZXJzZWN0aW9ucyBtaXN0ZXIgR2VvcmdlIHdpbGwgdmlzaXQuIEV2ZXJ5IHBhaXIgb2YgYWRqYWNlbnQgaW50ZWdlcnMgZGVub3RlcyBhIHN0cmVldCBoZSB3aWxsIHRyYXZlcnNlLiBUaGF0IHN0cmVldCB3aWxsIGV4aXN0IGFuZCBNaXN0ZXIgR2VvcmdlIHdpbGwgdHJhdmVyc2UgZXZlcnkgc3RyZWV0IGF0IG1vc3Qgb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiBhbmQgTCwgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGEgc3RyZWV0IGJldHdlZW4gaW50ZXJzZWN0aW9uIEEgYW5kIEIsIGFuZCBpdCB0YWtlcyBMIG1pbnV0ZXMgdG8gdHJhdmVyc2UuIEwgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDEwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZWFzdCBhbW91bnQgb2YgdGltZSAoaW4gbWludXRlcykgTHVrYSBuZWVkcyB0byBtYWtlIGhpcyBkZWxpdmVyeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: vjerksen