시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB225737724618.386%

문제

월드산의 하부에는 동굴로 들어가는 입구가 있는데, 동굴은 터널을 통해 서로 연결되어 있는 여러 개의 작은 방들로 구성되어 있다. 동굴 입구는 탐험의 시작점이 되는 방 (이하 시작방)으로 곧장 연결되어 있다. 각 방을 연결하는 터널은 서로 교차하지 않으며, 두 개의 방을 연결하는 터널은 많아 봐야 하나이다.

"원쌤배 동굴 탐험 대회"가 개최될 예정이다. 대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데, 그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다. 첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며, 둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. (시작방은 물론 두 번 방문하게 되므로 예외이다.)

유명한 동굴 탐험가 김진영은 대회에 참가하기 위해 오랜 준비를 했고, 동굴을 여러 번 사전 답사하여 동굴 내부 구조를 알아내는 데 성공했다. 각각의 터널에 대해, 그는 그 터널을 가로지르는 데 필요한 시간을 계산했는데, 터널을 어느 방향으로 가로지르느냐에 따라 걸리는 시간이 서로 다른 경우도 있을 수 있다고 한다. 동굴 입구와 시작방 사이에서 소요되는 시간이나, 방 내부에서 이동하는데 필요한 시간은 무시할 수 있을 만했다. 이제 그는 경기의 규칙을 만족시키면서도, 가장 짧은 시간 내에 완주할 수 있는 경로를 찾아내려고 한다. 그를 돕기 위한 프로그램을 작성하라.

입력

첫째 줄에 n과 m이 주어진다. (3 ≤ n ≤ 5000, 3 ≤ m ≤ 10000) 이는 각각 동굴 내부의 방의 개수와, 터널의 개수를 나타낸다.

이어지는 m개의 줄에는 각각 터널의 정보를 제공하는 네 개의 숫자 a, b, c, d가 포함되어 있다. 이것은 a번 방에서 b번 방으로 갈 때는 c의 시간이 걸리고, 반대로 b번 방에서 a번 방으로 갈 때는 d의 시간이 걸린다는 의미이다. (1 ≤a, b ≤ n. a ≠ b. 1 ≤ c, d ≤ 10000)

방의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 방이 시작방이다. 언제나 조건을 만족하는 경로가 하나는 있다고 가정해도 좋다.

출력

동굴 탐험에 소요되는 최소시간을 출력한다.

예제 입력 1

3 3
1 2 4 3
2 3 4 2
1 3 1 1

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjE4NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWFkNzQgXHVkMGQwXHVkNWQ4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDRcdWI0ZGNcdWMwYjBcdWM3NTggXHVkNTU4XHViZDgwXHVjNWQwXHViMjk0IFx1YjNkOVx1YWQ3NFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHVjNzg1XHVhZDZjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViM2Q5XHVhZDc0XHVjNzQwIFx1ZDEzMFx1YjExMFx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM3OTFcdWM3NDAgXHViYzI5XHViNGU0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjNkOVx1YWQ3NCBcdWM3ODVcdWFkNmNcdWIyOTQgXHVkMGQwXHVkNWQ4XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc3NCBcdWI0MThcdWIyOTQgXHViYzI5IChcdWM3NzRcdWQ1NTggXHVjMmRjXHVjNzkxXHViYzI5KVx1YzczY1x1Yjg1YyBcdWFjZTdcdWM3YTUgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YmMyOVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQwIFx1YjljZVx1YzU0NCBcdWJkMTBcdWM1N2MgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtcdWM2ZDBcdWMzMjRcdWJjMzAgXHViM2Q5XHVhZDc0IFx1ZDBkMFx1ZDVkOCBcdWIzMDBcdWQ2OGMmcXVvdDtcdWFjMDAgXHVhYzFjXHVjZDVjXHViNDIwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHViMzAwXHVkNjhjXHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWMyZGNcdWM3OTFcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1YjNkOVx1YWQ3NCBcdWIwYjRcdWJkODBcdWI5N2MgXHViMmVjXHViODI0LCBcdWIyZTRcdWMyZGMgXHVjMmRjXHVjNzkxXHViYzI5XHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NCBcdWM2NDAgXHViZTYwXHVjODM4IFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NzhcdWIzNzAsIFx1YWRmOCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjYzM4XHVhYzAwXHVjNzkwXHVhYzAwIFx1YjljOFx1Yzc0Y1x1YjMwMFx1Yjg1YyBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYyBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWNmMWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjODcwXHVhYzc0XHVjNzQwLCBcdWMyZGNcdWM3OTFcdWJjMjkgXHVjNzc0XHVjNjc4XHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWNkNWNcdWMxOGNcdWQ1NWMgXHVkNTU4XHViMDk4XHViMjk0IFx1YWM3MFx1Y2NkMFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViYTcwLCBcdWI0NThcdWM5ZjggXHVjODcwXHVhYzc0XHVjNzQwLCBcdWM1YjRcdWI1YTQgXHViYzI5XHVhY2ZjIFx1ZDEzMFx1YjExMFx1YjNjNCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YmM4OFx1YmMxNlx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIChcdWMyZGNcdWM3OTFcdWJjMjlcdWM3NDAgXHViYjNjXHViODYwIFx1YjQ1MCBcdWJjODggXHViYzI5XHViYjM4XHVkNTU4XHVhYzhjIFx1YjQxOFx1YmJjMFx1Yjg1YyBcdWM2MDhcdWM2NzhcdWM3NzRcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWJhODVcdWQ1NWMgXHViM2Q5XHVhZDc0IFx1ZDBkMFx1ZDVkOFx1YWMwMCBcdWFlNDBcdWM5YzRcdWM2MDFcdWM3NDAgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjI0XHViNzljIFx1YzkwMFx1YmU0NFx1Yjk3YyBcdWQ1ODhcdWFjZTAsIFx1YjNkOVx1YWQ3NFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzBhY1x1YzgwNCBcdWIyZjVcdWMwYWNcdWQ1NThcdWM1ZWMgXHViM2Q5XHVhZDc0IFx1YjBiNFx1YmQ4MCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxMzBcdWIxMTBcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWFkZjhcdWIyOTQgXHVhZGY4IFx1ZDEzMFx1YjExMFx1Yzc0NCBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTg4XHViMjk0XHViMzcwLCBcdWQxMzBcdWIxMTBcdWM3NDQgXHVjNWI0XHViMjkwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTBcdWIwZDBcdWM1ZDAgXHViNTMwXHViNzdjIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIzZDlcdWFkNzQgXHVjNzg1XHVhZDZjXHVjNjQwIFx1YzJkY1x1Yzc5MVx1YmMyOSBcdWMwYWNcdWM3NzRcdWM1ZDBcdWMxMWMgXHVjMThjXHVjNjk0XHViNDE4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjA5OCwgXHViYzI5IFx1YjBiNFx1YmQ4MFx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI5Y2NcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWFkZjhcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWJhNzRcdWMxMWNcdWIzYzQsIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMmRjXHVhYzA0IFx1YjBiNFx1YzVkMCBcdWM2NDRcdWM4ZmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjYzNlXHVjNTQ0XHViMGI0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOTdjIFx1YjNkNVx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBuICZsZTsgNTAwMCwgMyAmbGU7IG0gJmxlOyAxMDAwMCkgXHVjNzc0XHViMjk0IFx1YWMwMVx1YWMwMSBcdWIzZDlcdWFkNzQgXHViMGI0XHViZDgwXHVjNzU4IFx1YmMyOVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAsIFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjODFjXHVhY2Y1XHVkNTU4XHViMjk0IFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIGEsIGIsIGMsIGRcdWFjMDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQwIGFcdWJjODggXHViYzI5XHVjNWQwXHVjMTFjIGJcdWJjODggXHViYzI5XHVjNzNjXHViODVjIFx1YWMwOCBcdWI1NGNcdWIyOTQgY1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWFjXHVhY2UwLCBcdWJjMThcdWIzMDBcdWI4NWMgYlx1YmM4OCBcdWJjMjlcdWM1ZDBcdWMxMWMgYVx1YmM4OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YjU0Y1x1YjI5NCBkXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiAoMSAmbGU7YSwgYiAmbGU7IG4uIGEgJm5lOyBiLiAxICZsZTsgYywgZCAmbGU7IDEwMDAwKTxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWM1ZWMgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgMVx1YmM4OCBcdWJjMjlcdWM3NzQgXHVjMmRjXHVjNzkxXHViYzI5XHVjNzc0XHViMmU0LiBcdWM1YjhcdWM4MWNcdWIwOTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVkNTU4XHViMDk4XHViMjk0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NzRcdWIzYzQgXHVjODhiXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjNkOVx1YWQ3NCBcdWQwZDBcdWQ1ZDhcdWM1ZDAgXHVjMThjXHVjNjk0XHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTg0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBDb21wZXRpdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+QXQgdGhlIGZvb3Qgb2YgTXQuIEJ5dGUgdGhlcmUgaXMgYW4gZW50cmFuY2UgdG8gYSBjYXZlLiBUaGUgY2F2ZSBjb25zaXN0cyBvZiBhIGNvbXBsZXggc3lzdGVtIG9mIGNoYW1iZXJzIGNvbm5lY3RlZCB3aXRoIHR1bm5lbHMuIFRoZSBjYXZlIGVudHJhbmNlIGxlYWRzIHN0cmFpZ2h0IHRvIGEgY2hhbWJlciBjYWxsZWQgdGhlIGZyb250IGNoYW1iZXIuIFRoZSB0dW5uZWxzIGRvIG5vdCBpbnRlcnNlY3QgKHRoZXkgbWVldCBvbmx5IGluIGNoYW1iZXJzKS4gVHdvIGNoYW1iZXJzIGNhbiBlaXRoZXIgYmUgY29ubmVjdGVkIHdpdGggYSBzaW5nbGUgdHVubmVsLCBvciBub3QgYmUgY29ubmVjdGVkIGF0IGFsbCAoaXQgbWF5LCBob3dldmVyLCBiZSBwb3NzaWJsZSB0byByZWFjaCBvbmUgY2hhbWJlciBmcm9tIHRoZSBvdGhlciB2aWEgcmVtYWluaW5nIGNoYW1iZXJzKS4gQSB0dW5uZWwgYWx3YXlzIGNvbm5lY3RzIHR3byBkaXN0aW5jdCBjaGFtYmVycy48XC9wPlxyXG5cclxuPHA+SXQgaGFzIGJlZW4gZGVjaWRlZCB0aGF0ICYjMzk7S2luZyYjMzk7cyBvZiBCeXRlb3RpYSBDdXAmIzM5OyBjb21wZXRpdGlvbiBpcyB0byBiZSBvcmdhbml6ZWQuIFRoZSBnb2FsIG9mIGVhY2ggY29tcGV0aXRvciBpcyB0byB0cmF2ZXJzZSBhIGZyZWVseSBjaG9zZW4gcm91dGUgaW4gdGhlIGNhdmUgYW5kIGdldCBvdXQgYXMgcXVpY2tseSBhcyBwb3NzaWJsZS4gVGhlIHJvdXRlIGhhcyB0byBsZWFkIHRocm91Z2ggYXQgbGVhc3Qgb25lIG90aGVyIGNoYW1iZXIgdGhhbiB0aGUgZnJvbnQgb25lLiBPbmx5IHR3byBydWxlcyBhcmUgaW4gZm9yY2U6IGR1cmluZyB0aGUgdHJhdmVsIHRocm91Z2ggdGhlIGNhdmUgZWFjaCBjaGFtYmVyICh3aXRoIHRoZSBleGNlcHRpb24gb2YgdGhlIGZyb250IGNoYW1iZXIpIGNhbiBiZSB2aXNpdGVkIG9uY2UgYXQgdGhlIG1vc3QsIHNpbWlsYXJseSBlYWNoIGNvcnJpZG9yIGNhbm5vdCBiZSBjcm9zc2VkIG1vcmUgdGhhbiBvbmNlLjxcL3A+XHJcblxyXG48cD5BIGZhbW91cyBjYXZlIGV4cGxvcmVyIEJ5dGVhbGEgaXMgcHJlcGFyaW5nIGhpbXNlbGYgZm9yIHRoZSBjb21wZXRpdGlvbi4gQnl0ZWFsYSBoYXMgYmVlbiB0cmFpbmluZyBpbiB0aGUgY2F2ZSBmb3IgYSBsb25nIHRpbWUgYW5kIGhlIGhhcyBhY3F1aXJlZCBhIGRldGFpbGVkIGtub3dsZWRnZSBvZiB0aGUgY29ycmlkb3Igc3lzdGVtLiBGb3IgZWFjaCBjb3JyaWRvciBoZSBoYXMgY2FsY3VsYXRlZCB0aGUgYW1vdW50IG9mIHRpbWUgbmVlZGVkIHRvIGNyb3NzIGl0IGluIGVhY2ggZGlyZWN0aW9uLiBUaGUgdGltZSBuZWNlc3NhcnkgdG8gbW92ZSB3aXRoaW4gdGhlIGNoYW1iZXJzIGNhbiBiZSBuZWdsZWN0ZWQuIE5vdyBCeXRlYWxhIHdvdWxkIGxpa2UgdG8gY2FsY3VsYXRlIGEgcm91dGUgc2F0aXNmeWluZyByZXF1aXJlbWVudHMgb2YgdGhlIGNvbXBldGl0aW9uLCB3aGljaCBjYW4gYmUgdHJhdmVyc2VkIGluIHRoZSBsZWFzdCB0aW1lIHBvc3NpYmxlICh0aGUgdGltZSBuZWNlc3NhcnkgdG8gdHJhdmVyc2UgYSByb3V0ZSBpcyB0aGUgc3VtIG9mIHRoZSB0aW1lcyBuZWVkZWQgdG8gY3Jvc3MgY29ycmlkb3JzIHdoaWNoIGl0IGNvbnNpc3RzIG9mKS48XC9wPlxyXG5cclxuPHA+SGVscCBCeXRlYWxhISBXcml0ZSBhIHByb2dyYW1tZSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBhIGRlc2NyaXB0aW9uIG9mIHRoZSBjYXZlIGFuZCB0aW1lcyBuZWNlc3NhcnkgdG8gY3Jvc3MgZWFjaCBjb3JyaWRvciw8XC9saT5cclxuXHQ8bGk+Y2FsY3VsYXRlcyBhIHJvdXRlIGNvbnNpc3RlbnQgd2l0aCB0aGUgcmVxdWlyZW1lbnRzLCBmb3Igd2hpY2ggdGhlIHN1bSBvZiB0aW1lcyBuZWVkZWQgdG8gY3Jvc3MgdGhlIGNvcnJpZG9ycyBpdCBjb21wcmlzZXMgaXMgbWluaW1hbCw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQgdGhlIHRpbWUgcmVxdWlyZWQgdG8gdHJhdmVyc2UgdGhlIGNhbGN1bGF0ZWQgcm91dGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB0aGVyZSBhcmUgdHdvIGludGVnZXJzIG4gYW5kIG0gKDMgJmxlOyBuICZsZTsgNSAwMDAsIDMgJmxlOyBtICZsZTsgMTAgMDAwKSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgYW5kIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgY2hhbWJlcnMgaW4gdGhlIGNhdmUgYW5kIHRoZSBudW1iZXIgb2YgaW50ZXJsaW5raW5nIGNvcnJpZG9ycywgcmVzcGVjdGl2ZWx5LiBUaGUgY2hhbWJlcnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGUgZnJvbnQgY2hhbWJlciBpcyBkZW5vdGVkIGJ5IDEuIFRoZSBmb2xsb3dpbmcgbSBsaW5lcyBjb250YWluIGEgZGVzY3JpcHRpb24gb2YgdGhlIGNvcnJpZG9ycy4gSW4gZWFjaCBvZiB0aGVzZSBsaW5lcyB0aGVyZSBhcmUgZm91ciBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gQSA0LXR1cGxlIGEsYixjLGQgbWVhbnMgdGhhdCBjaGFtYmVycyBhIGFuZCBiIGFyZSBjb25uZWN0ZWQgd2l0aCBhIGNvcnJpZG9yLCB0aGUgY3Jvc3NpbmcgdGltZSBmcm9tIGEgdG8gYiBpcyBjIGFuZCBmcm9tIGIgdG8gYSBpcyBkLCAxICZsZTsgYSxiICZsZTsgbiwgYSAmbmU7IGIsIDEgJmxlOyBjLGQgJmxlOyAxMCAwMDAuIFlvdSBjYW4gYXNzdW1lIHRoYXQgYSByb3V0ZSBzYXRpc2Z5aW5nIHJlcXVpcmVtZW50cyBvZiB0aGUgY29tcGV0aXRpb24gYWx3YXlzIGV4aXN0cy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtbWUgc2hvdWxkIHdyaXRlIGluIHRoZSBmaXJzdCAoYW5kIG9ubHkpIGxpbmUgb2YgdGhlIG91dHB1dCBvbmUgaW50ZWdlciAtIHRoZSBtaW5pbWFsIHRpbWUgcmVxdWlyZWQgdG8gdHJhdmVyc2UgYSByb3V0ZSBzYXRpc2Z5aW5nIGNvbmRpdGlvbnMgb2YgdGhlIGNvbXBldGl0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 1 4번

  • 데이터를 추가한 사람: ntopia