시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 367 103 72 36.923%

문제

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

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

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

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

예를 들어, 고둘라가 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개 줄에는 도로의 정보를 나타내는 세 정수 U, V, L이 주어진다. 교차로 U와 V를 연결하는 도로를 이동하는데 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
W3sicHJvYmxlbV9pZCI6IjI5ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmRcdWM2NTVcdWM3NTggXHViYzI5XHViYjM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIwOWNcdWM4ZmNcdWM1ZDAgXHVjMGMxXHVhZGY4XHViMmM4IFx1YzU0NFx1Yjc3Y1x1YmU0NFx1YzU0NFx1Yzc1OCBcdWFkNmRcdWM2NTUgXHVhY2UwXHViNDU4XHViNzdjIFx1Y2MzZFx1YzljMFx1Yzk4OCBcdWM2MDFcdWMwYWNcdWM2YjBcdWI0ZGNcdWFjMDAgXHVkNTVjXHVhZDZkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1YjJlNC4gXHVhY2UwXHViNDU4XHViNzdjXHViMjk0IFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWNiZFx1Y2MzMFx1Yzc0MCBcdWFkZjhcdWFjMDAgXHVkMGMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWI3YzlcdWM3NzQgXHVhZTM4XHVjNWQwIFx1YzljNFx1Yzc4NVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOFx1YWMwMCBcdWFlMzhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNkOVx1YzU0OFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjYzI4XHViN2M5XHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyYyBcdWMyMTggXHVjNWM2XHVhYzhjIFx1ZDFiNVx1YzgxY1x1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZGY4XHVhYzAwIFx1YzljNFx1Yzc4NVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWJkODBcdWQxMzAgXHVhZTM4XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWNjMjhcdWI3YzlcdWM3NDAgXHVhY2M0XHVjMThkIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjI0XHVkMWEwXHViYzE0XHVjNzc0IFx1YzE4Y1x1YjE0NCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM3NTggXHViNGE0XHViOTdjIFx1Yzc3NFx1YzViNCBcdWFkZmNcdWNjOThcdWM1ZDBcdWMxMWMgXHVkNTNjXHVjNzkwXHViOTdjIFx1ZDJiOFx1YjdlZFx1YzczY1x1Yjg1YyBcdWJjMzBcdWIyZWNcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZDUwXHVkMWI1IFx1ZDFiNVx1YzgxYyBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1YzgxNVx1YzJkY1x1YzVkMCBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTc0XHVjMTFjIFx1YzllNFx1YjliNFx1YmVkNFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYmY4IFx1YWNlMFx1YjQ1OFx1Yjc3YyBcdWNjM2RcdWM5YzBcdWM5ODggXHVjNjAxXHVjMGFjXHVjNmIwXHViNGRjXHViMjk0IFx1YzBjMVx1YWRmOFx1YjJjOCBcdWM1NDRcdWI3N2NcdWJlNDRcdWM1NDRcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzE0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWQ1NWNcdWFkNmRcdWM1ZDAgXHVjNjU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNWI0XHViNWE0IFx1YWUzOFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTg4XHVjNWI0XHVjNTdjIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWJlNjBcdWI5NzRcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVhY2JkXHViODVjXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzJkY1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzY0MCBcdWFkNTBcdWNjMjhcdWI4NWNcdWI5N2MgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViODVjIFx1YmFhOFx1YjM3OFx1YjljMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjZTBcdWI0NThcdWI3N2NcdWFjMDAgXHVhZGY4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YjNjNCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCAxMFx1YmQ4NFx1Yzc3NCBcdWI0MThcdWIzNTggXHViNTRjXHVjNWQwIFx1YzViNFx1YjVhNCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTg4XHVhY2UwLCBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IDVcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZmMgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1YjI5NCAxMCwgMTEsIDEyLCAxMywgMTRcdWJkODRcdWM1ZDBcdWIyOTQgXHVjOWM0XHVjNzg1XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCA5XHViZDg0IFx1Yzc3NFx1YzgwNCwgMTVcdWJkODQgXHVjNzc0XHVkNmM0XHVjNWQwIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHVjOWM0XHVjNzg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YWNlMCBLXHViZDg0XHVjNzc0IFx1YzljMFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDUwXHVjYzI4XHViODVjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMDAsIDIgJmxlOyBNICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggQSwgQiwgSywgR1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSwgQiAmbGU7IE4sIDAgJmxlOyBLICZsZTsgMTAwMCwgMCAmbGU7IEcgJmxlOyAxMDAwKSBBXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWQ1MFx1Y2MyOFx1Yjg1YywgQlx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM3NzRcdWIyZTQuIEtcdWIyOTQgXHVhY2UwXHViNDU4XHViNzdjXHVhYzAwIFx1Y2Q5Y1x1YmMxY1x1ZDU1YyBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2Q5Y1x1YmMxY1x1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NTggXHVjYzI4XHVjNzc0LCBHXHViMjk0IFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHVhZDUwXHVjYzI4XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBHXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuXHVjNzc0IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFjZTBcdWI0NThcdWI3N2NcdWFjMDAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjNzc4XHVjODExXHVkNTVjIFx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWNlMFx1YjQ1OFx1Yjc3Y1x1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViM2M0XHViODVjXHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjEzN1x1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBVLCBWLCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZDUwXHVjYzI4XHViODVjIFVcdWM2NDAgVlx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBMXHViZDg0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIExcdWM3NDAgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTgyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0VPUkdFIiwiZGVzY3JpcHRpb24iOiI8cD5MYXN0IHdlZWsgTWlzdGVyIEdlb3JnZSB2aXNpdGVkIENyb2F0aWEuIFNpbmNlIE1pc3RlciBHZW9yZ2UgaXMgYSB2ZXJ5IGltcG9ydGFudCBwZXJzb24sIHdoaWxlIGhlIHdhcyBpbiBhIHN0cmVldCwgdGhlIHBvbGljZSBkaXNhbGxvd2VkIGVudHJ5IHRvIHRoYXQgc3RyZWV0LCBidXQgdmVoaWNsZXMgdGhhdCBlbnRlcmVkIHRoZSBzdHJlZXQgYmVmb3JlIE1pc3RlciBHZW9yZ2UgY291bGQgY29udGludWUgZHJpdmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hpbGUgTWlzdGVyIEdlb3JnZSB3YXMgdmlzaXRpbmcsIEx1a2EgZHJvdmUgaGlzIHRydWNrIGFyb3VuZCB0b3duLiBCdXQgYmVjYXVzZSBvZiBzb21lIG9mIHRoZSBzdHJlZXRzIGJlaW5nIGNsb3NlZCBvZmYsIGhlIGNvdWxkbiYjMzk7dCBtYWtlIGhpcyBkZWxpdmVyeSBpbiB0aW1lIGFuZCBhbG1vc3QgbG9zdCBoaXMgam9iLiBBbHRob3VnaCBpdCBpcyBsYXRlIG5vdywgaGUgaXMgd29uZGVyaW5nIGhvdyBoZSBjb3VsZCBoYXZlIHBsYW5uZWQgaGlzIGRlbGl2ZXJ5IGJldHRlciBpLmUuIHdoYXQgd291bGQgaGF2ZSBiZWVuIHRoZSBsZWFzdCB0aW1lIG5lZWRlZCB0byBtYWtlIGhpcyBkZWxpdmVyeSB3aGlsZSBNaXN0ZXIgR2VvcmdlIHdhcyB2aXNpdGluZy4gSGUga25vd3MgdGhlIHJvdXRlIG1pc3RlciBHZW9yZ2UgdG9vay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNpdHkgaXMgbW9kZWxlZCB3aXRoIGludGVyc2VjdGlvbnMgYW5kIHR3by13YXkgc3RyZWV0cyBjb25uZWN0aW5nIHRoZW0uIEZvciBlYWNoIHN0cmVldCwgTHVrYSBrbm93cyBob3cgbXVjaCB0aW1lIGhlIG5lZWRzIHRvIHRyYXZlcnNlIGl0IChtaXN0ZXIgR2VvcmdlIG5lZWRzIHRoZSBzYW1lIGFtb3VudCBvZiB0aW1lKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIE1pc3RlciBHZW9yZ2Ugc3RhcnRzIHRyYXZlcnNpbmcgYSBzdHJlZXQgZHVyaW5nIG1pbnV0ZSAxMCBhbmQgbmVlZHMgNSBtaW51dGVzIHRvIGV4aXQgaXQsIHRoaXMgc3RyZWV0IHdpbGwgYmUgYmxvY2tlZCBkdXJpbmcgbWludXRlcyAxMCwgMTEsIDEyLCAxMyBhbmQgMTQuIEx1a2EgY2FuIGVudGVyIHRoZSBzdHJlZXQgZHVyaW5nIG1pbnV0ZXMgOSBhbmQgZWFybGllciwgb3IgMTUgYW5kIGxhdGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBsZWFzdCBhbW91bnQgb2YgdGltZSBMdWthIG5lZWRzIHRvIG1ha2UgaGlzIGRlbGl2ZXJ5LCBpZiBoZSBzdGFydHMgZHJpdmluZyBLIG1pbnV0ZXMgYWZ0ZXIgdGhlIGFycml2YWwgb2YgTWlzdGVyIEdlb3JnZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgyICZsZTsgTiAmbGU7IDEwMDAsIDIgJmxlOyBNICZsZTsgMTAgMDAwKSwgdGhlIG51bWJlciBvZiBpbnRlcnNlY3Rpb25zIGFuZCB0aGUgbnVtYmVyIG9mIHN0cmVldHMuIFRoZSBpbnRlcnNlY3Rpb25zIGFyZSBudW1iZXJlZCAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBmb3VyIGludGVnZXJzIEEsIEIsIEsgYW5kIEcgKDEgJmxlOyBBLCBCICZsZTsgTiwgMCAmbGU7IEsgJmxlOyAxMDAwLCAwICZsZTsgRyAmbGU7IDEwMDApLiBUaGVzZSBhcmUsIGluIG9yZGVyOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBpbnRlcnNlY3Rpb24gd2hlcmUgTHVrYSBzdGFydHM7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBpbnRlcnNlY3Rpb24gTHVrYSBtdXN0IGdldCB0bzsmbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIGRpZmZlcmVuY2UgaW4gc3RhcnRpbmcgdGltZXMgYmV0d2VlbiBtaXN0ZXIgR2VvcmdlIGFuZCBMdWthIChMdWthIHN0YXJ0cyBhdCBpbnRlcnNlY3Rpb24gQSBleGFjdGx5IEsgbWludXRlcyBhZnRlciBtaXN0ZXIgR2VvcmdlIHN0YXJ0cyBoaXMgcm91dGUpOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgb24gTWlzdGVyIEdlb3JnZSYjMzk7cyByb3V0ZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBHIGludGVnZXJzLCB0aGUgbGFiZWxzIG9mIGludGVyc2VjdGlvbnMgbWlzdGVyIEdlb3JnZSB3aWxsIHZpc2l0LiBFdmVyeSBwYWlyIG9mIGFkamFjZW50IGludGVnZXJzIGRlbm90ZXMgYSBzdHJlZXQgaGUgd2lsbCB0cmF2ZXJzZS4gVGhhdCBzdHJlZXQgd2lsbCBleGlzdCBhbmQgTWlzdGVyIEdlb3JnZSB3aWxsIHRyYXZlcnNlIGV2ZXJ5IHN0cmVldCBhdCBtb3N0IG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIgYW5kIEwsIG1lYW5pbmcgdGhhdCB0aGVyZSBpcyBhIHN0cmVldCBiZXR3ZWVuIGludGVyc2VjdGlvbiBBIGFuZCBCLCBhbmQgaXQgdGFrZXMgTCBtaW51dGVzIHRvIHRyYXZlcnNlLiBMIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbGVhc3QgYW1vdW50IG9mIHRpbWUgKGluIG1pbnV0ZXMpIEx1a2EgbmVlZHMgdG8gbWFrZSBoaXMgZGVsaXZlcnkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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