시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB74835319638.431%

문제

때는 2020년, 당신과 그 일행은 좀비로 황폐화된 대도시의 어느 마을 안에 갇혔다. 당신들 또한 바이러스에 감염되었기 때문에 좀비가 되기 전에 빨리 병원을 찾아 치료해야 한다. 당신들은 과학자이기에 멍청하게 좀비들에게 돌격해 길을 뚫기보다는 좀비들 몰래 슬금슬금 이동하는 게 안전하다. 하지만 도처에 널린 것이 좀비라 몇몇 도로는 다른 곳보다 슬금슬금 지나가는 데 시간이 많이 걸린다. 때로는 다같이 다니는 것보다 여러 무리로 떨어져서 각자 나아가는 게 훨씬 안전할 것이다.

게다가, 이 좀비들은 크게 감염되지는 않아서 머리 뒤편에 눈이 달려있거나 하지는 않다. 따라서 몇몇 도로는 한쪽 방향으로 이동하는 건 쉽지만, 역행하는 것은 어렵거나 불가능할지도 모른다.

당신들 일행 중 최대 몇 명이 좀비가 되기 전에 좀비들을 피해서 병원에 도달할 수 있을까?

입력

첫째 줄에 테스트 케이스의 개수가 주어지며, 각 테스트 케이스는 다음과 같이 이루어져 있다. 주어지는 모든 값은 정수이다.

  • 첫째 줄에 장소의 개수 n이 주어진다. (1 ≤ n ≤ 1 000)
  • 다음 줄에 일행이 처음에 있던 장소 i, 일행의 사람 수 g, 좀비에 감염되기까지 걸리는 시간 s가 주어진다. (1 ≤ i ≤ n, 1 ≤ g ≤ 100, 1 ≤ s ≤ 100)
    • s초에 병원에 도착한 경우 좀비가 되기 전에 병원을 찾은 것이다.
  • 다음 줄에 병원의 수 m이 주어진다. (1 ≤ m ≤ n)
  • 이어서 m개의 줄에 각 병원이 위치한 장소 번호가 주어진다. (1 ≤ x ≤ n)
  • 다음 줄에 도로의 개수 r이 주어진다. (0 ≤ r ≤ 1 000)
  • 이어서 r개의 줄에 각 도로의 정보를 나타내는 값 a, b, p, t가 주어진다. (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ p ≤ 100, 1 ≤ t ≤ 100) 이 도로는 a에서 b로 가는 도로이며, 매 단위시간마다 p명이 도로에 들어설 수 있으며 지나가려면 단위시간 t가 소요된다는 뜻이다.

어떤 장소 쌍에 대해 도로는 최대 2개(한 방향당 1개)까지 존재한다. 각 장소는 충분히 안전하여 얼마든지 가만히 서서 기다려도 안전하다. 또한 한 장소에 있을 수 있는 사람 수에도 제한이 없다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 감염되지 않고 병원에 도달하는 최대 사람 수를 출력한다.

예제 입력 1

2
4
3 8 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3
4
3 10 5
2
2
4
5
1 2 1 3
3 2 1 4
3 1 2 1
1 4 1 3
3 4 1 3

예제 출력 1

8
9
W3sicHJvYmxlbV9pZCI6IjEwMzE5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODgwXHViZTQ0IFx1YzU0NFx1ZDNlY1x1Y2U3Y1x1YjliZFx1YzJhNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNTRjXHViMjk0IDIwMjBcdWIxNDQsIFx1YjJmOVx1YzJlMFx1YWNmYyBcdWFkZjggXHVjNzdjXHVkNTg5XHVjNzQwIFx1Yzg4MFx1YmU0NFx1Yjg1YyBcdWQ2NjlcdWQzZDBcdWQ2NTRcdWI0MWMgXHViMzAwXHViM2M0XHVjMmRjXHVjNzU4IFx1YzViNFx1YjI5MCBcdWI5YzhcdWM3NDQgXHVjNTQ4XHVjNWQwIFx1YWMwN1x1ZDYxNFx1YjJlNC4gXHViMmY5XHVjMmUwXHViNGU0IFx1YjYxMFx1ZDU1YyBcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTRcdWM1ZDAgXHVhYzEwXHVjNWZjXHViNDE4XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4ODBcdWJlNDRcdWFjMDAgXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWJlNjhcdWI5YWMgXHViY2QxXHVjNmQwXHVjNzQ0IFx1Y2MzZVx1YzU0NCBcdWNlNThcdWI4Y2NcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIyZjlcdWMyZTBcdWI0ZTRcdWM3NDAgXHVhY2ZjXHVkNTU5XHVjNzkwXHVjNzc0XHVhZTMwXHVjNWQwIFx1YmE0ZFx1Y2NhZFx1ZDU1OFx1YWM4YyBcdWM4ODBcdWJlNDRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViM2NjXHVhY2E5XHVkNTc0IFx1YWUzOFx1Yzc0NCBcdWI2YWJcdWFlMzBcdWJjZjRcdWIyZTRcdWIyOTQgXHVjODgwXHViZTQ0XHViNGU0IFx1YmFiMFx1Yjc5OCBcdWMyYWNcdWFlMDhcdWMyYWNcdWFlMDggXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM4YyBcdWM1NDhcdWM4MDRcdWQ1NThcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWIzYzRcdWNjOThcdWM1ZDAgXHViMTEwXHViOWIwIFx1YWM4M1x1Yzc3NCBcdWM4ODBcdWJlNDRcdWI3N2MgXHViYTg3XHViYTg3IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWIyZTRcdWI5NzggXHVhY2YzXHViY2Y0XHViMmU0IFx1YzJhY1x1YWUwOFx1YzJhY1x1YWUwOCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHViMzcwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWI1NGNcdWI4NWNcdWIyOTQgXHViMmU0XHVhYzE5XHVjNzc0IFx1YjJlNFx1YjJjOFx1YjI5NCBcdWFjODNcdWJjZjRcdWIyZTQgXHVjNWVjXHViN2VjIFx1YmIzNFx1YjlhY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM4MzhcdWMxMWMgXHVhYzAxXHVjNzkwIFx1YjA5OFx1YzU0NFx1YWMwMFx1YjI5NCBcdWFjOGMgXHVkNmU4XHVjNTJjIFx1YzU0OFx1YzgwNFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1YjJlNFx1YWMwMCwgXHVjNzc0Jm5ic3A7XHVjODgwXHViZTQ0XHViNGU0XHVjNzQwIFx1ZDA2Y1x1YWM4YyBcdWFjMTBcdWM1ZmNcdWI0MThcdWM5YzBcdWIyOTQgXHVjNTRhXHVjNTQ0XHVjMTFjIFx1YmEzOFx1YjlhYyBcdWI0YTRcdWQzYjhcdWM1ZDAgXHViMjA4XHVjNzc0IFx1YjJlY1x1YjgyNFx1Yzc4OFx1YWM3MFx1YjA5OCBcdWQ1NThcdWM5YzBcdWIyOTQgXHVjNTRhXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHViYTg3XHViYTg3IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWQ1NWNcdWNhYmQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjNzQgXHVjMjdkXHVjOWMwXHViOWNjLCBcdWM1ZWRcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzViNFx1YjgzNVx1YWM3MFx1YjA5OCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NjBcdWM5YzBcdWIzYzQgXHViYWE4XHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWI0ZTQgXHVjNzdjXHVkNTg5IFx1YzkxMSBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4NVx1Yzc3NCBcdWM4ODBcdWJlNDRcdWFjMDAgXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWM4ODBcdWJlNDRcdWI0ZTRcdWM3NDQgXHVkNTNjXHVkNTc0XHVjMTFjIFx1YmNkMVx1YzZkMFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXNlcnVwbG9hZFwva2tzMjI3XC8yMDE2MDgwNlwvYWY1Y2I4MGI3Y2YzZjk4MTJmNjU4ZmQ1Y2VjNDljNTUucG5nXCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YWMxMlx1Yzc0MCZuYnNwO1x1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVjN2E1XHVjMThjXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IG4gJmxlOyAxIDAwMCk8XC9saT5cclxuXHQ8bGk+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWM3N2NcdWQ1ODlcdWM3NzQgXHVjYzk4XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWM3YTVcdWMxOGMgaSwgXHVjNzdjXHVkNTg5XHVjNzU4IFx1YzBhY1x1Yjc4YyBcdWMyMTggZywgXHVjODgwXHViZTQ0XHVjNWQwIFx1YWMxMFx1YzVmY1x1YjQxOFx1YWUzMFx1YWU0Y1x1YzljMCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0IHNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgaSAmbGU7IG4sJm5ic3A7MSAmbGU7IGcgJmxlOyAxMDAsJm5ic3A7MSAmbGU7IHMgJmxlOyAxMDApXHJcblx0PHVsPlxyXG5cdFx0PGxpPnNcdWNkMDhcdWM1ZDAgXHViY2QxXHVjNmQwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1YyBcdWFjYmRcdWM2YjAgXHVjODgwXHViZTQ0XHVhYzAwIFx1YjQxOFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViY2QxXHVjNmQwXHVjNzQ0IFx1Y2MzZVx1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHViY2QxXHVjNmQwXHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IG0gJmxlOyBuKTxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWM1YjRcdWMxMWMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YmNkMVx1YzZkMFx1Yzc3NCBcdWM3MDRcdWNlNThcdWQ1NWMgXHVjN2E1XHVjMThjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyB4ICZsZTsgbik8XC9saT5cclxuXHQ8bGk+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4IHJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygwICZsZTsgciAmbGU7IDEgMDAwKTxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWM1YjRcdWMxMWMgclx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWMxMiBhLCBiLCBwLCB0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IGEsIGIgJmxlOyBuLCZuYnNwO2EgJm5lOyZuYnNwO2IsJm5ic3A7MSAmbGU7IHAgJmxlOyAxMDAsJm5ic3A7MSAmbGU7IHQgJmxlOyAxMDApIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWIyOTQgYVx1YzVkMFx1YzExYyBiXHViODVjIFx1YWMwMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NzRcdWJhNzAsIFx1YjllNCBcdWIyZThcdWM3MDRcdWMyZGNcdWFjMDRcdWI5YzhcdWIyZTQgcFx1YmE4NVx1Yzc3NCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViNGU0XHVjNWI0XHVjMTI0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVjOWMwXHViMDk4XHVhYzAwXHViODI0XHViYTc0IFx1YjJlOFx1YzcwNFx1YzJkY1x1YWMwNCZuYnNwO3RcdWFjMDAgXHVjMThjXHVjNjk0XHViNDFjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjN2E1XHVjMThjIFx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjXHViMjk0IFx1Y2Q1Y1x1YjMwMCAyXHVhYzFjKFx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWIyZjkgMVx1YWMxYylcdWFlNGNcdWM5YzAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjN2E1XHVjMThjXHViMjk0IFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWM1NDhcdWM4MDRcdWQ1NThcdWM1ZWMgXHVjNWJjXHViOWM4XHViNGUwXHVjOWMwJm5ic3A7XHVhYzAwXHViOWNjXHVkNzg4IFx1YzExY1x1YzExYyBcdWFlMzBcdWIyZTRcdWI4MjRcdWIzYzQgXHVjNTQ4XHVjODA0XHVkNTU4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVkNTVjIFx1YzdhNVx1YzE4Y1x1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGMgXHVjMjE4XHVjNWQwXHViM2M0IFx1YzgxY1x1ZDU1Y1x1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzEwXHVjNWZjXHViNDE4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWJjZDFcdWM2ZDBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWMwYWNcdWI3OGMgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDMxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkF2b2lkaW5nIHRoZSBBcG9jYWx5cHNlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYW5kIHRoZSByZXN0IG9mIHlvdXIgdGVhbSBhcmUgc3R1Y2sgaW4gYSB0b3duIGR1cmluZyB0aGUgem9tYmllIGFwb2NhbHlwc2Ugb2YgMjAyMC4gWW91IGFsbCBtaWdodCBiZSBpbmZlY3RlZCB3aXRoIHRoZSB2aXJ1cyBhbmQgaGVuY2UgeW91IHdpbGwgaGF2ZSB0byBmaW5kIHlvdXIgd2F5IHRvIG9uZSBvZiB0aGUgbWVkaWNhbCBmYWNpbGl0aWVzIHRvIGdldCBhIGN1cmUgYmVmb3JlIHlvdSBhbHNvIGJlY29tZSB6b21iaWVzLiBCZWNhdXNlIHlvdSBhcmUgc2NpZW50aXN0cyB5b3UgcXVpY2tseSByZWFsaXplIHRoYXQgaXQgaXMgc2FmZXIgdG8gdHJ5IGFuZCBzbmVhayB5b3VyIHdheSBwYXN0IHRoZSB6b21iaWVzIHRoYW4gdG8gcmVja2xlc3NseSBzdGFydCBmaWdodGluZyB0aGVtLiBPYnZpb3VzbHkgdGhlIHpvbWJpZXMgYXJlIGV2ZXJ5d2hlcmUgc28gc29tZSBzdHJlZXRzIG1pZ2h0IHRha2UgbW9yZSB0aW1lIHRvIHNuZWFrIHRocm91Z2ggdGhhbiBvdGhlcnMuIEl0IGlzIGFsc28gb2J2aW91cyB0aGF0IGJ5IHNwbGl0dGluZyB1cCBpbnRvIHNtYWxsZXIgZ3JvdXBzIGl0IGlzIGVhc2llciB0byBtb3ZlIGFyb3VuZCB1bmRldGVjdGVkLjxcL3A+XHJcblxyXG48cD5GdXJ0aGVybW9yZSwgc2luY2UgdGhlc2Ugem9tYmllcyBoYXZlIG5vdCBtdXRhdGVkIHRvIHRoZSBleHRlbnQgdGhhdCB0aGV5IGFjdHVhbGx5IGhhdmUgZXllcyBpbiB0aGUgYmFjayBvZiB0aGVpciBoZWFkcywgaXQgbWlnaHQgYmUgZWFzeSB0byBjcm9zcyBzb21lIHN0cmVldHMgaW4gb25lIGRpcmVjdGlvbiB3aGlsZSBoYXJkIG9yIGltcG9zc2libGUgdG8gY3Jvc3MgdGhlbSBpbiB0aGUgb3RoZXIgZGlyZWN0aW9uLjxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBvZiB5b3UgY2FuIHNuZWFrIHBhc3QgYWxsIHRoZSB6b21iaWVzIGFuZCBnZXQgdG8gYSBtZWRpY2FsIGZhY2lsaXR5IGluIHRpbWU/PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48YSBocmVmPVwiaHR0cHM6XC9cL3hrY2QuY29tXC83MzRcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlczJcL291dGJyZWFrLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1MnB4OyB3aWR0aDo3NDBweFwiIFwvPjxcL2E+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2YgbG9jYXRpb25zIGluIHRoZSB0b3duLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBpLCBnIGFuZCBzICgxICZsZTsgaSAmbGU7IG4gYW5kIDEgJmxlOyBnICZsZTsgMTAwIGFuZCAxICZsZTsgcyAmbGU7IDEwMCk6IHRoZSBzdGFydGluZyBsb2NhdGlvbiBvZiB5b3VyIGdyb3VwLCB0aGUgbnVtYmVyIG9mIHBlb3BsZSBpbiBpdCwgYW5kIHRoZSBudW1iZXIgb2YgdGltZSBzdGVwcyB5b3UgaGF2ZSB0byBnZXQgdG8gdGhlIHNhZmV0eSBvZiBhIG1lZGljYWwgZmFjaWxpdHksIHJlc3BlY3RpdmVseS48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIG0gKDEgJmxlOyBtICZsZTsgbik6IHRoZSBudW1iZXIgb2YgbWVkaWNhbCBmYWNpbGl0aWVzIGluIHRoZSB0b3duLjxcL2xpPlxyXG5cdDxsaT5tIGxpbmVzLCBlYWNoIHdpdGggYSBzaW5nbGUgaW50ZWdlciB4ICgxICZsZTsgeCAmbGU7IG4pOiB0aGUgbG9jYXRpb24gb2YgZWFjaCBvZiB0aGUgbWVkaWNhbCBmYWNpbGl0aWVzLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgciAoMCAmbGU7IHIgJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2Ygcm9hZHMgaW4gdGhlIHRvd24uPFwvbGk+XHJcblx0PGxpPnIgbGluZXMsIGVhY2ggd2l0aCBmb3VyIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBhLCBiLCBwIGFuZCB0ICgxICZsZTsgYSwgYiAmbGU7IG4gYW5kIGEgJm5lOyZuYnNwO2IgYW5kIDEgJmxlOyBwICZsZTsgMTAwIGFuZCAxICZsZTsgdCAmbGU7IDEwMCksIGluZGljYXRpbmcgdGhhdCB0aGVyZSBpcyBhIHJvYWQgZnJvbSBhIHRvIGIsIHdoaWNoIHAgcGVvcGxlIGNhbiBlbnRlciBhdCBldmVyeSB0aW1lIHN0ZXAgYW5kIHRha2VzIHQgdGltZXN0ZXBzIHRvIHRyYXZlcnNlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXJlIGFyZSBhdCBtb3N0IHR3byByb2FkcyAmbmRhc2g7IG9uZSBpbiBlYWNoIGRpcmVjdGlvbiAmbmRhc2g7IGJldHdlZW4gYW55IHBhaXIgb2YgbG9jYXRpb25zLiBUaGUgbG9jYXRpb25zIGFyZSBzYWZlIGVub3VnaCB0byB3YWl0IGF0IGZvciBhbnkgYW1vdW50IG9mIHRpbWUgYW5kIGRvIG5vdCBoYXZlIGEgbGltaXQgb24gdGhlIG51bWJlciBvZiBwZW9wbGUgdGhhdCBjYW4gYmUgdGhlcmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHA+b25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcGVvcGxlIHRoYXQgY2FuIGdldCB0byBhIG1lZGljYWwgZmFjaWxpdHkgaW4gdGltZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2014 A번