29796번
- 헤카톤
다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 168 | 57 | 53 | 37.324% |
문제
짐은 불멸의 존재이니라!
거대한 성의 모습을 가진 매우 강력한 괴물, 헤카톤과의 전투는 기나긴 전쟁으로 바뀌고 있는 참이다. 막대한 위력 앞에 서 있는 용사들은 이 거대한 적에 맞서기 위해 모든 힘을 쏟아붓고 있다.
월드 레이드 파티의 조사 끝에 헤카톤은 총 $N$곳의 약점을 가지고 있음이 밝혀졌다. 이 약점들은 각자 독립된 체력을 갖고 있으며, 각각에 충분히 많은 데미지를 주고 모든 약점의 체력을 $0$으로 만들어야만 헤카톤을 쓰러뜨릴 수 있다. 지금 $i$번째 약점에서는 $A_i$명의 용사들이 헤카톤을 공격하고 있다.
그러나 헤카톤을 공격하고 있던 싶프트는 이상한 상황을 발견했다. 많은 용사들이 체력이 이미 많이 소진된 약점에 집중되어 있었고, 오히려 체력이 아직 꽤 남아 있는 약점에는 공격하는 용사가 거의 없는 상황이었던 것이다.
싶프트는 전투가 끝없이 이어진다면 용사들이 체력과 의지를 모두 잃게 될 것으로 우려했다. 그래서 그녀는 체력이 많이 남은 약점들에 집중적으로 용사를 배치하여 공격을 가하는 전략을 생각했다. 하지만 헤카톤의 압도적인 거대함 때문에 약점들 사이의 거리는 상당하다. 따라서 용사들을 재배치하더라도 그들이 현재 위치에서 이동하기 용이한 약점들로만 이동시키는 것이 효율적이라는 결론을 내렸다.
이제 싶프트는 이동하기 용이한 약점들의 쌍과 집중 공격이 필요한 약점들이 주어졌을 때 용사들을 적절히 재배치하여 각 약점에 최소 몇 명의 용사들이 있도록 할 수 있는지 알고 싶다. 헤카톤과의 전투에서 승리하기 위해, 그녀의 전략이 실행될 수 있을지 빠르게 판단하는 프로그램을 작성하자.
입력
첫 번째 줄에는 헤카톤의 약점의 개수 $N$와 이동하기 용이한 약점의 쌍의 개수 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 100;$ $1 \le M \le 1\,000)$
다음 줄에는 지금 헤카톤의 약점을 공격하고 있는 용사의 수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 100\,000)$
다음 $M$개의 각 줄에 정수 $u_i, v_i$가 공백으로 구분되어 주어진다. $(1 \le u_i,v_i \le N;$ $u_i \ne v_i)$ 이는 $u_i$번째 약점과 $v_i$번째 약점 사이가 이동하기 용이하다는 것을 의미한다. 다만, 이는 $u_i$번째 약점으로부터 이동하기 용이한 약점들이 $v_i$번째 약점으로부터도 이동하기 용이한 것임을 의미하는 것은 아니며, 반대의 경우도 그러함에 주의하라. 하나의 약점 쌍에 대해 이 정보는 중복되어 주어지지 않는다.
다음 줄에는 집중 공격이 필요한 약점의 개수 $R$이 주어진다. $(1 \le R \le N)$
다음 줄에는 집중 공격이 필요한 약점 번호 $B_1, B_2, \cdots, B_R$이 공백으로 구분되어 주어진다. 같은 약점 번호가 두 번 이상 주어지는 경우는 없다. $(1 \le B_i \le N)$
출력
용사들을 적절히 재배치했을 때 각 약점에 최소 몇 명의 용사들이 있도록 할 수 있는지 출력한다.
제한
예제 입력 1
5 4 2 3 4 1 0 1 3 2 3 3 4 3 5 2 3 5
예제 출력 1
4
$3$번과 $5$번 약점에 지원이 필요한 상황이다.
- $3$번 약점에 있던 $4$명의 용사를 모두 $5$번 약점으로 재배치한다.
- $1$번 약점의 $2$명과 $2$번 약점의 $1$명, 그리고 $4$번 약점의 $1$명을 $3$번 약점으로 재배치한다.
이렇게 재배치했을 때, $3$번 약점과 $5$번 약점에서는 각각 최소 $4$명씩의 용사가 공격하게 된다. 각각의 약점에 최소 $5$명 이상씩을 배치하는 방법은 없으므로, 이 경우가 최적이다.
예제 입력 2
4 3 10 0 0 0 1 2 2 3 3 4 1 4
예제 출력 2
0
$1$번 약점에서 공격하던 용사들이 $4$번 약점까지 이동하기에는 $1$번 약점과 $4$번 약점은 너무 멀리 떨어져 있다.
노트
W3sicHJvYmxlbV9pZCI6IjI5Nzk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNWU0XHVjZTc0XHVkMWE0IiwiZGVzY3JpcHRpb24iOiI8YmxvY2txdW90ZT48c3Ryb25nPlx1YzlkMFx1Yzc0MCBcdWJkODhcdWJhNzhcdWM3NTggXHVjODc0XHVjN2FjXHVjNzc0XHViMmM4XHViNzdjITxcL3N0cm9uZz48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC83ZmJlM2Y3Ni1kOWJhLTQ1MTYtODUwYy02NjY4NGIzODkzMzhcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDY4M3B4OyBtYXgtd2lkdGg6IDEwMCVcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzcwXHViMzAwXHVkNTVjIFx1YzEzMVx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NDQgXHVhYzAwXHVjOWM0IFx1YjllNFx1YzZiMCBcdWFjMTVcdWI4MjVcdWQ1NWMgXHVhZDM0XHViYjNjLCA8c3Ryb25nPlx1ZDVlNFx1Y2U3NFx1ZDFhNDxcL3N0cm9uZz5cdWFjZmNcdWM3NTggXHVjODA0XHVkMjJjXHViMjk0IFx1YWUzMFx1YjA5OFx1YWUzNCBcdWM4MDRcdWM3YzFcdWM3M2NcdWI4NWMgXHViYzE0XHViMDBjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWNjMzhcdWM3NzRcdWIyZTQuIFx1YjljOVx1YjMwMFx1ZDU1YyBcdWM3MDRcdWI4MjUgXHVjNTVlXHVjNWQwIFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjNmE5XHVjMGFjXHViNGU0XHVjNzQwIFx1Yzc3NCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHVjODAxXHVjNWQwIFx1YjlkZVx1YzExY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHViYWE4XHViNGUwIFx1ZDc5OFx1Yzc0NCBcdWMzZGZcdWM1NDRcdWJkOTNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDRcdWI0ZGMgXHViODA4XHVjNzc0XHViNGRjIFx1ZDMwY1x1ZDJmMFx1Yzc1OCBcdWM4NzBcdWMwYWMgXHViMDVkXHVjNWQwIFx1ZDVlNFx1Y2U3NFx1ZDFhNFx1Yzc0MCBcdWNkMWQgJE4kXHVhY2YzXHVjNzU4IFx1YzU3ZFx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzRjXHVjNzc0IFx1YmMxZFx1ZDYwMFx1Yzg0Y1x1YjJlNC4gXHVjNzc0IFx1YzU3ZFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWM3OTAgXHViM2M1XHViOWJkXHViNDFjIFx1Y2NiNFx1YjgyNVx1Yzc0NCBcdWFjMTZcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDFcdWFjMDFcdWM1ZDAgXHVjZGE5XHViZDg0XHVkNzg4IFx1YjljZVx1Yzc0MCBcdWIzNzBcdWJiZjhcdWM5YzBcdWI5N2MgXHVjOGZjXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWM1N2RcdWM4MTBcdWM3NTggXHVjY2I0XHViODI1XHVjNzQ0ICQwJFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2NcdWI5Y2MgXHVkNWU0XHVjZTc0XHVkMWE0XHVjNzQ0IFx1YzRmMFx1YjdlY1x1YjcyOFx1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5YzBcdWFlMDggJGkkXHViYzg4XHVjOWY4IFx1YzU3ZFx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCAkQV9pJFx1YmE4NVx1Yzc1OCBcdWM2YTlcdWMwYWNcdWI0ZTRcdWM3NzQgXHVkNWU0XHVjZTc0XHVkMWE0XHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMzYyMzNiYWQtYTNlNS00MmExLWI0ZDItMDY0YjM4ZWUyMTAxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImltYWdlLXJlbmRlcmluZzogcGl4ZWxhdGVkO1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIwOTggXHVkNWU0XHVjZTc0XHVkMWE0XHVjNzQ0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIzNTggPHN0cm9uZz5cdWMyZjZcdWQ1MDRcdWQyYjg8XC9zdHJvbmc+XHViMjk0IFx1Yzc3NFx1YzBjMVx1ZDU1YyBcdWMwYzFcdWQ2NjlcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWI5Y2VcdWM3NDAgXHVjNmE5XHVjMGFjXHViNGU0XHVjNzc0IFx1Y2NiNFx1YjgyNVx1Yzc3NCBcdWM3NzRcdWJiZjggXHViOWNlXHVjNzc0IFx1YzE4Y1x1YzljNFx1YjQxYyBcdWM1N2RcdWM4MTBcdWM1ZDAgXHVjOWQxXHVjOTExXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzVjOFx1YWNlMCwgXHVjNjI0XHVkNzg4XHViODI0IFx1Y2NiNFx1YjgyNVx1Yzc3NCBcdWM1NDRcdWM5YzEgXHVhZjY0IFx1YjBhOFx1YzU0NCBcdWM3ODhcdWIyOTQgXHVjNTdkXHVjODEwXHVjNWQwXHViMjk0IFx1YWNmNVx1YWNhOVx1ZDU1OFx1YjI5NCBcdWM2YTlcdWMwYWNcdWFjMDAgXHVhYzcwXHVjNzU4IFx1YzVjNlx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM3NzRcdWM1YzhcdWIzNTggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZjZcdWQ1MDRcdWQyYjhcdWIyOTQgXHVjODA0XHVkMjJjXHVhYzAwIFx1YjA1ZFx1YzVjNlx1Yzc3NCBcdWM3NzRcdWM1YjRcdWM5YzRcdWIyZTRcdWJhNzQgXHVjNmE5XHVjMGFjXHViNGU0XHVjNzc0IFx1Y2NiNFx1YjgyNVx1YWNmYyBcdWM3NThcdWM5YzBcdWI5N2MgXHViYWE4XHViNDUwIFx1Yzc4M1x1YWM4YyBcdWI0MjAgXHVhYzgzXHVjNzNjXHViODVjIFx1YzZiMFx1YjgyNFx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YWRmOFx1YjE0MFx1YjI5NCBcdWNjYjRcdWI4MjVcdWM3NzQgXHViOWNlXHVjNzc0IFx1YjBhOFx1Yzc0MCBcdWM1N2RcdWM4MTBcdWI0ZTRcdWM1ZDAgXHVjOWQxXHVjOTExXHVjODAxXHVjNzNjXHViODVjIFx1YzZhOVx1YzBhY1x1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NThcdWM1ZWMgXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkNWU0XHVjZTc0XHVkMWE0XHVjNzU4IFx1YzU1NVx1YjNjNFx1YzgwMVx1Yzc3OCBcdWFjNzBcdWIzMDBcdWQ1NjggXHViNTRjXHViYjM4XHVjNWQwIFx1YzU3ZFx1YzgxMFx1YjRlNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YzBjMVx1YjJmOVx1ZDU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzZhOVx1YzBhY1x1YjRlNFx1Yzc0NCBcdWM3YWNcdWJjMzBcdWNlNThcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZGY4XHViNGU0XHVjNzc0IFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzZhOVx1Yzc3NFx1ZDU1YyBcdWM1N2RcdWM4MTBcdWI0ZTRcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzRcdWI3N2NcdWIyOTQgXHVhY2IwXHViODYwXHVjNzQ0IFx1YjBiNFx1YjgzOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzJmNlx1ZDUwNFx1ZDJiOFx1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNmE5XHVjNzc0XHVkNTVjIFx1YzU3ZFx1YzgxMFx1YjRlNFx1Yzc1OCBcdWMzMGRcdWFjZmMgXHVjOWQxXHVjOTExIFx1YWNmNVx1YWNhOVx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTdkXHVjODEwXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjNmE5XHVjMGFjXHViNGU0XHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWM3YWNcdWJjMzBcdWNlNThcdWQ1NThcdWM1ZWMgXHVhYzAxIFx1YzU3ZFx1YzgxMFx1YzVkMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmE4NVx1Yzc1OCBcdWM2YTlcdWMwYWNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViM2M0XHViODVkIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWIyZTQuIFx1ZDVlNFx1Y2U3NFx1ZDFhNFx1YWNmY1x1Yzc1OCBcdWM4MDRcdWQyMmNcdWM1ZDBcdWMxMWMgXHVjMmI5XHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhZGY4XHViMTQwXHVjNzU4IFx1YzgwNFx1YjdiNVx1Yzc3NCBcdWMyZTRcdWQ1ODlcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWJlNjBcdWI5NzRcdWFjOGMgXHVkMzEwXHViMmU4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1ZTRcdWNlNzRcdWQxYTRcdWM3NTggXHVjNTdkXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCAkTiRcdWM2NDAgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzZhOVx1Yzc3NFx1ZDU1YyBcdWM1N2RcdWM4MTBcdWM3NTggXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOCAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMiBcXGxlIE4gXFxsZSAxMDA7JCAkMSBcXGxlIE0gXFxsZSAxXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWFlMDggXHVkNWU0XHVjZTc0XHVkMWE0XHVjNzU4IFx1YzU3ZFx1YzgxMFx1Yzc0NCBcdWFjZjVcdWFjYTlcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzZhOVx1YzBhY1x1Yzc1OCBcdWMyMTggJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDAgXFxsZSBBX2kgXFxsZSAxMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE0kXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICR1X2ksIHZfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIHVfaSx2X2kgXFxsZSBOOyQgJHVfaSBcXG5lIHZfaSkkIFx1Yzc3NFx1YjI5NCAkdV9pJFx1YmM4OFx1YzlmOCBcdWM1N2RcdWM4MTBcdWFjZmMgJHZfaSRcdWJjODhcdWM5ZjggXHVjNTdkXHVjODEwIFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNmE5XHVjNzc0XHVkNTU4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1YjljYywgXHVjNzc0XHViMjk0ICR1X2kkXHViYzg4XHVjOWY4IFx1YzU3ZFx1YzgxMFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNmE5XHVjNzc0XHVkNTVjIFx1YzU3ZFx1YzgxMFx1YjRlNFx1Yzc3NCAkdl9pJFx1YmM4OFx1YzlmOCBcdWM1N2RcdWM4MTBcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzBcdWIzYzQgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzZhOVx1Yzc3NFx1ZDU1YyBcdWFjODNcdWM3ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCA8dT5cdWM1NDRcdWIyYzhcdWJhNzA8XC91PiwgXHViYzE4XHViMzAwXHVjNzU4IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWFkZjhcdWI3ZWNcdWQ1NjhcdWM1ZDAgXHVjOGZjXHVjNzU4XHVkNTU4XHViNzdjLiBcdWQ1NThcdWIwOThcdWM3NTggXHVjNTdkXHVjODEwIFx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBcdWM5MTFcdWJjZjVcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVjOTExIFx1YWNmNVx1YWNhOVx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTdkXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCAkUiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBSIFxcbGUgTikkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVjOTExIFx1YWNmNVx1YWNhOVx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNTdkXHVjODEwIFx1YmM4OFx1ZDYzOCAkQl8xLCBCXzIsIFxcY2RvdHMsIEJfUiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM1N2RcdWM4MTAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiAkKDEgXFxsZSBCX2kgXFxsZSBOKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2YTlcdWMwYWNcdWI0ZTRcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YzdhY1x1YmMzMFx1Y2U1OFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVhYzAxIFx1YzU3ZFx1YzgxMFx1YzVkMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmE4NVx1Yzc1OCBcdWM2YTlcdWMwYWNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViM2M0XHViODVkIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+JDMkXHViYzg4XHVhY2ZjICQ1JFx1YmM4OCBcdWM1N2RcdWM4MTBcdWM1ZDAgXHVjOWMwXHVjNmQwXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMwYzFcdWQ2NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JDMkXHViYzg4IFx1YzU3ZFx1YzgxMFx1YzVkMCBcdWM3ODhcdWIzNTggJDQkXHViYTg1XHVjNzU4IFx1YzZhOVx1YzBhY1x1Yjk3YyBcdWJhYThcdWI0NTAgJDUkXHViYzg4IFx1YzU3ZFx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3YWNcdWJjMzBcdWNlNThcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQxJFx1YmM4OCBcdWM1N2RcdWM4MTBcdWM3NTggJDIkXHViYTg1XHVhY2ZjICQyJFx1YmM4OCBcdWM1N2RcdWM4MTBcdWM3NTggJDEkXHViYTg1LCBcdWFkZjhcdWI5YWNcdWFjZTAgJDQkXHViYzg4IFx1YzU3ZFx1YzgxMFx1Yzc1OCAkMSRcdWJhODVcdWM3NDQgJDMkXHViYzg4IFx1YzU3ZFx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3YWNcdWJjMzBcdWNlNThcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0XHViODA3XHVhYzhjIFx1YzdhY1x1YmMzMFx1Y2U1OFx1ZDU4OFx1Yzc0NCBcdWI1NGMsICQzJFx1YmM4OCBcdWM1N2RcdWM4MTBcdWFjZmMgJDUkXHViYzg4IFx1YzU3ZFx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWFjMDFcdWFjMDEgXHVjZDVjXHVjMThjICQ0JFx1YmE4NVx1YzUyOVx1Yzc1OCBcdWM2YTlcdWMwYWNcdWFjMDAgXHVhY2Y1XHVhY2E5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzU3ZFx1YzgxMFx1YzVkMCBcdWNkNWNcdWMxOGMgJDUkXHViYTg1IFx1Yzc3NFx1YzBjMVx1YzUyOVx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YywgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPiQxJFx1YmM4OCBcdWM1N2RcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhY2Y1XHVhY2E5XHVkNTU4XHViMzU4Jm5ic3A7XHVjNmE5XHVjMGFjXHViNGU0XHVjNzc0ICQ0JFx1YmM4OCBcdWM1N2RcdWM4MTBcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwXHVjNWQwXHViMjk0ICQxJFx1YmM4OCBcdWM1N2RcdWM4MTBcdWFjZmMgJDQkXHViYzg4IFx1YzU3ZFx1YzgxMFx1Yzc0MCBcdWIxMDhcdWJiMzQgXHViYTQwXHViOWFjIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk3OTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIZWthdG9uIiwiZGVzY3JpcHRpb24iOiI8YmxvY2txdW90ZT48ZW0+PGI+SSBhbSBpbW1vcnRhbCE8XC9iPjxcL2VtPjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzdmYmUzZjc2LWQ5YmEtNDUxNi04NTBjLTY2Njg0YjM4OTMzOFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjgzcHg7IG1heC13aWR0aDogMTAwJVwiIFwvPjxcL3A+XHJcblxyXG48cD5BbiBpbnRlbnNlIGJhdHRsZSByYWdlcyBhZ2FpbnN0IHRoZSBtaWdodHkgYm9zcyBpbiBhIHZpc2FnZSBvZiBhIGNvbG9zc2FsIGZvcnRyZXNzLCA8ZW0+SGVrYXRvbjxcL2VtPiwgdGhyZWF0ZW5pbmcgdG8gZXZvbHZlIGludG8gYSBwcm90cmFjdGVkIHdhci4gSGVyb2VzIHN0YW5kaW5nIGluIHRoZSBmYWNlIG9mIHRoaXMgaW1tZW5zZSBwb3dlciBwb3VyIG91dCB0aGVpciB1dG1vc3Qgc3RyZW5ndGggdG8gc3RhbmQgYWdhaW5zdCB0aGlzIGdhcmdhbnR1YW4gZm9lLjxcL3A+XHJcblxyXG48cD5UaHJvdWdoIHJpZ29yb3VzIHJlc2VhcmNoIG9mIHRoZSBXb3JsZCBSYWlkIFBhcnR5LCBpdCBoYXMgYmVlbiByZXZlYWxlZCB0aGF0IEhla2F0b24gcG9zc2Vzc2VzIGEgdG90YWwgb2YgJE4kIHdlYWsgcG9pbnRzLiBUaGVzZSB3ZWFrIHBvaW50cyBlYWNoIGhhdmUgdGhlaXIgZGlzdGluY3QgSFAgdmFsdWVzLiBUbyBkZWZlYXQgSGVrYXRvbiwgb25lIG11c3QgaW5mbGljdCBhbXBsZSBkYW1hZ2UgdG8gcmVkdWNlIHRoZSBIUCBvZiBhbGwgdGhlc2Ugd2VhayBwb2ludHMgdG8gJDAkLiBDdXJyZW50bHksICRBX2kkXHUyMDBiIGhlcm9lcyBhcmUgYXR0YWNraW5nIHRoZSAkaSQtdGggd2VhayBwb2ludCBvZiBIZWthdG9uLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzM2MjMzYmFkLWEzZTUtNDJhMS1iNGQyLTA2NGIzOGVlMjEwMVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJpbWFnZS1yZW5kZXJpbmc6IHBpeGVsYXRlZDtcIiBcLz48XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgPGVtPlNoaWZmdDxcL2VtPiwgYW1pZHN0IGhlciBhdHRhY2sgb24gSGVrYXRvbiwgZGlzY2VybmVkIGFuIGFsYXJtaW5nIHNpdHVhdGlvbi4gTWFueSBoZXJvZXMgd2VyZSBjb25jZW50cmF0ZWQgb24gd2VhayBwb2ludHMgd2hlcmUgSFAgd2FzIGFscmVhZHkgc2lnbmlmaWNhbnRseSBkZXBsZXRlZCwgd2hlcmVhcyB0aG9zZSB3ZWFrIHBvaW50cyBzdGlsbCBicmltbWluZyB3aXRoIEhQIGhhZCBzY2FyY2VseSBhbnkgaGVyb2VzIGF0dGFja2luZyB0aGVtLjxcL3A+XHJcblxyXG48cD5GZWFyaW5nIHRoYXQgdGhlIHByb3RyYWN0aW9uIG9mIHRoaXMgYmF0dGxlIHdvdWxkIHNhcCBhbGwgc3RyZW5ndGggYW5kIHdpbGxwb3dlciBvZiB0aGUgaGVyb2VzLCBTaGlmZnQgZGV2aXNlZCBhIHN0cmF0ZWd5IHRvIGZvY3VzIGF0dGFja3MgbW9yZSBvbiB0aGUgd2VhayBwb2ludHMgd2l0aCBzaWduaWZpY2FudCBoZWFsdGguIEhvd2V2ZXIsIGR1ZSB0byBIZWthdG9uJiMzOTtzIG92ZXJ3aGVsbWluZyBzaXplLCB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGVzZSB3ZWFrIHBvaW50cyBpcyBzdWJzdGFudGlhbC4gSGVuY2UsIHNoZSBjb25jbHVkZWQgdGhhdCBldmVuIGlmIHRoZSBoZXJvZXMgd2VyZSB0byBiZSByZWFycmFuZ2VkLCBpdCB3b3VsZCBiZSBtb3N0IGVmZmVjdGl2ZSB0byBtb3ZlIHRoZW0gb25seSB0byB0aGUgd2VhayBwb2ludHMgdGhhdCBhcmUgZWFzeSB0byBhY2Nlc3MgZnJvbSB0aGVpciBjdXJyZW50IHBvc2l0aW9ucy48XC9wPlxyXG5cclxuPHA+Tm93LCBnaXZlbiB0aGUgcGFpcnMgb2YgZWFzaWx5IGFjY2Vzc2libGUgd2VhayBwb2ludHMgYW5kIHRob3NlIHdlYWsgcG9pbnRzIHRoYXQgbmVlZCBmb2N1c2VkIGF0dGFja3MsIFNoaWZmdCZuYnNwO3dpc2hlcyB0byBrbm93IHRoZSBtaW5pbXVtIG51bWJlciBvZiBoZXJvZXMgdGhhdCBjYW4gYmUgYWxsb2NhdGVkIHRvIGVhY2ggd2VhayBwb2ludCBhZnRlciBhbiBlZmZpY2llbnQgcmVhcnJhbmdlbWVudC4gVG8gZW5zdXJlIHZpY3RvcnkgYWdhaW5zdCBIZWthdG9uLCB3cml0ZSBhIHByb2dyYW0gdGhhdCBxdWlja2x5IGRldGVybWluZXMgaWYgaGVyIHN0cmF0ZWd5IGNhbiBiZSBlZmZlY3RpdmVseSBleGVjdXRlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTiQgYW5kICRNJCAkKDImbmJzcDtcXGxlIE4gXFxsZSAxMDA7JCZuYnNwOyQxIFxcbGUgTSBcXGxlIDFcXCwwMDApJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIEhla2F0b24mIzM5O3Mgd2VhayBwb2ludHMgYW5kIHRoZSBudW1iZXIgb2YgcGFpcnMgb2Ygd2VhayBwb2ludHMgdGhhdCBhcmUgZWFzaWx5IGFjY2Vzc2libGUuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgaW50ZWdlcnMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kICQoMCBcXGxlIEFfaSBcXGxlIDEwMFxcLDAwMCkkLCZuYnNwO3NlcGFyYXRlZCBieSBzcGFjZXMmbmJzcDsmbWRhc2g7IHRoZSBudW1iZXIgb2YgaGVyb2VzIGN1cnJlbnRseSBhdHRhY2tpbmcgZWFjaCBvZiBIZWthdG9uJiMzOTtzIHdlYWsgcG9pbnRzLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nICRNJCBsaW5lcyBlYWNoIGNvbnRhaW4gdHdvIGludGVnZXJzICR1X2kkIGFuZCAkdl9pJCAkKDEgXFxsZSB1X2ksdl9pIFxcbGUgTjskICR1X2kgXFxuZSB2X2kpJCwmbmJzcDtzZXBhcmF0ZWQgYnkgYSBzcGFjZTombmJzcDtUaGlzIGltcGxpZXMgdGhhdCBpdCBpcyBlYXN5IHRvIG1vdmUgYmV0d2VlbiB0aGUgJHVfaSQtdGhcdTIwMGIgd2VhayBwb2ludCBhbmQgdGhlICR2X2kkLXRoXHUyMDBiIHdlYWsgcG9pbnQuIE5vdGUgdGhhdCB0aGlzIGRvZXMgPHU+bm90PFwvdT4mbmJzcDtuZWNlc3NhcmlseSBtZWFuJm5ic3A7dGhhdCB0aGUgd2VhayBwb2ludHMgZWFzaWx5IGFjY2Vzc2libGUgZnJvbSAkdl9pJC10aFx1MjAwYiBhcmUgYWxzbyBlYXNpbHkgYWNjZXNzaWJsZSBmcm9tICR1X2kkLXRoXHUyMDBiLCBhbmQgdmljZSB2ZXJzYS4gSW5mb3JtYXRpb24gYWJvdXQgYSBwYWlyIG9mIHdlYWsgcG9pbnRzIHdpbGwgbm90IGJlIGdpdmVuIG1vcmUgdGhhbiBvbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgJFIkICQoMSBcXGxlIFIgXFxsZSBOKSQgJm1kYXNoOyZuYnNwO3RoZSBudW1iZXIgb2Ygd2VhayBwb2ludHMgdGhhdCByZXF1aXJlIGNvbmNlbnRyYXRlZCBhdHRhY2tzLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zICRSJCBpbnRlZ2VycyZuYnNwOyRCXzEsIEJfMiwgXFxjZG90cywgQl9SJCAkKDEgXFxsZSBCX2kgXFxsZSBOKSQsJm5ic3A7c2VwYXJhdGVkIGJ5IHNwYWNlcyAmbWRhc2g7IHRoZSBpbmRpY2VzIG9mIHRoZSB3ZWFrIHBvaW50cyB0aGF0IG5lZWQgY29uY2VudHJhdGVkIGF0dGFja3MuJm5ic3A7VGhlIHNhbWUmbmJzcDtpbmRleCBpcyBuZXZlciBnaXZlbiBtb3JlIHRoYW4gb25jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGhlcm9lcyB0aGF0IGNhbiBiZSBhbGxvY2F0ZWQgdG8gZWFjaCB3ZWFrIHBvaW50IGFmdGVyIGFuIGVmZmljaWVudCByZWFycmFuZ2VtZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+SW4gdGhlIGdpdmVuIHNjZW5hcmlvLCByZWluZm9yY2VtZW50cyBhcmUgcmVxdWlyZWQgYXQgdGhlICQzJHJkIGFuZCAkNSR0aCB3ZWFrIHBvaW50cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BbGwgJDQkIGhlcm9lcyBzdGF0aW9uZWQgYXQgdGhlICQzJHJkIHdlYWsgcG9pbnQgYXJlIHJlYXNzaWduZWQgdG8gdGhlICQ1JHRoIHdlYWsgcG9pbnQuPFwvbGk+XHJcblx0PGxpPkZyb20gdGhlICQxJHN0IHdlYWsgcG9pbnQsICQyJCBoZXJvZXMsIGZyb20gdGhlICQyJG5kIHdlYWsgcG9pbnQsICQxJCBoZXJvLCBhbmQgZnJvbSB0aGUgJDQkdGggd2VhayBwb2ludCwgJDEkIGhlcm8gYXJlIHJlbG9jYXRlZCB0byB0aGUgJDMkcmQgd2VhayBwb2ludC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5XaXRoIHRoaXMgcmVhbGxvY2F0aW9uLCB0aGUgJDMkcmQgYW5kICQ1JHRoIHdlYWsgcG9pbnRzIHJlY2VpdmUgYXR0YWNrcyBmcm9tIGF0IGxlYXN0ICQ0JCBoZXJvZXMgZWFjaC4gVGhlcmUgaXMgbm8gbWV0aG9kIHRvIGFsbG9jYXRlIGF0IGxlYXN0ICQ1JCBvciBtb3JlIGhlcm9lcyB0byBlYWNoIHdlYWsgcG9pbnQsIHRodXMgdGhpcyBhcnJhbmdlbWVudCBpcyBvcHRpbWFsLiZuYnNwOzxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5UaGUgaGVyb2VzIGF0dGFja2luZyBmcm9tIHRoZSAkMSRzdCB3ZWFrIHBvaW50IGNhbm5vdCBtb3ZlIHRvIHRoZSAkNCR0aCB3ZWFrIHBvaW50LCBhcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgJDEkc3QgYW5kICQ0JHRoIHdlYWsgcG9pbnRzIGlzIHRvbyBncmVhdC48XC9wPlxyXG4ifV0=
출처
Contest > BOJ User Contest > 임스의 메이플컵 > 제1회 임스의 메이플컵 (The 1st lms0806's Maple Cup) G번
- 문제를 만든 사람: shiftpsh
- 문제를 검수한 사람: cologne, tony9402, utilforever