시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB144301619.277%

문제

현재 W국은 N개의 나라와 전쟁 중이다. W국의 전력이 월등히 우세하여 전쟁에서 승리하는 것은 시간 문제이다. W국은 첩자를 통해, N개의 나라들 중 M개의 나라만을 정복하면 나머지 나라는 자동으로 항복한다는 정보를 입수했다.

이제 M개의 나라를 적당히 골라서 정복하려고 하는데, 각 나라마다 정복하는 데 걸리는 시간이 다르다. 어떤 나라는 오래 걸리고, 어떤 나라는 매우 순식간에 정복할 수도 있다. 단 그 나라를 정복하는 데 온 전력을 집중해야 하기 때문에, 매 순간 오직 한 나라와만 전쟁을 진행할 수 있다. 우리는 최대한 빨리 M개의 나라를 정복하려고 한다.

단, N개의 나라 사이에는 속국 관계가 존재할 수 있다. 나라 A가 나라 B의 속국인 경우, 나라 B를 정복하면 나라 B의 모든 속국들이 자동으로 항복하게 된다. 속국에는 서로 계층 관계가 존재해서, 나라 A가 나라 B의 속국이고, 나라 B가 나라 C의 속국인 경우, 나라 C를 정복하면 나라 A와 나라 B 모두 자동으로 정복하는 효과를 얻는다. 즉 자신의 속국과, 속국들의 속국과, 속국들의 속국들의 속국과, . . . 이렇게 모든 하위의 나라들이 자동으로 항복하게 된다.

나라 A가 나라 B의 속국이면서 동시에 나라 C의 속국일 수 없다. 즉 속국이라면 오직 한 나라의 속국일 뿐이다. 하지만 나라 A, 나라 B, ... 등 여러 나라가 한 나라의 속국일 수는 물론 있다.

N, M이 주어지고, 속국 관계가 주어지고, 각 나라를 정복하는 데 드는 일수가 주어지면, 최대한 빨리 M개의 나라를 정복할 수 있는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나라의 개수 N(1≤N≤200)과 M(0≤M≤N)이 주어진다. 이어서 N개의 줄에 각 나라에 대한 정보가 주어지는데, 먼저 나라의 이름이 문자열로 주어진다. 문자열의 길이는 1 이상 100 이하이며 알파벳 대소문자로 이루어져 있다. 이어서 빈 칸 뒤에 이 나라를 정복하는 데 드는 일수가 주어진다. 이어서 빈 칸이 주어지고 여러 개의 나라 이름들이 빈 칸을 사이에 두고 주어질 수가 있는데, 이 뒤에 주어지는 나라들이 바로 현재 나라의 속국들이 된다.

출력

첫째 줄에 M개의 나라를 최대한 빨리 정복하려고 할 때 며칠이 걸리는지 출력한다.

예제 입력 1

3 2
CountryA 10
CountryB 20 CountryA
CountryC 15

예제 출력 1

20

힌트

CountryB만 정복하면 자동으로 CountryB의 속국인 CountryA가 정복되어 2개 나라를 정복할 수 있다.
W3sicHJvYmxlbV9pZCI6IjEyMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWM3YzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYwNFx1YzdhYyBXXHVhZDZkXHVjNzQwIE5cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHVjNjQwIFx1YzgwNFx1YzdjMSBcdWM5MTFcdWM3NzRcdWIyZTQuIFdcdWFkNmRcdWM3NTggXHVjODA0XHViODI1XHVjNzc0IFx1YzZkNFx1YjRmMVx1ZDc4OCBcdWM2YjBcdWMxMzhcdWQ1NThcdWM1ZWMgXHVjODA0XHVjN2MxXHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjMmRjXHVhYzA0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC4gV1x1YWQ2ZFx1Yzc0MCBcdWNjYTlcdWM3OTBcdWI5N2MgXHVkMWI1XHVkNTc0LCBOXHVhYzFjXHVjNzU4IFx1YjA5OFx1Yjc3Y1x1YjRlNCBcdWM5MTEgTVx1YWMxY1x1Yzc1OCBcdWIwOThcdWI3N2NcdWI5Y2NcdWM3NDQgXHVjODE1XHViY2Y1XHVkNTU4XHViYTc0IFx1YjA5OFx1YmEzOFx1YzljMCBcdWIwOThcdWI3N2NcdWIyOTQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1ZDU2ZFx1YmNmNVx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzg1XHVjMjE4XHVkNTg4XHViMmU0LjxcL3A+XHJcbjxwPlx1Yzc3NFx1YzgxYyBNXHVhYzFjXHVjNzU4IFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWM4MDFcdWIyZjlcdWQ3ODggXHVhY2U4XHViNzdjXHVjMTFjIFx1YzgxNVx1YmNmNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWIwOThcdWI3N2NcdWI5YzhcdWIyZTQgXHVjODE1XHViY2Y1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjA5OFx1Yjc3Y1x1YjI5NCBcdWM2MjRcdWI3OTggXHVhYzc4XHViOWFjXHVhY2UwLCBcdWM1YjRcdWI1YTQgXHViMDk4XHViNzdjXHViMjk0IFx1YjllNFx1YzZiMCBcdWMyMWNcdWMyZGRcdWFjMDRcdWM1ZDAgXHVjODE1XHViY2Y1XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjJlOCBcdWFkZjggXHViMDk4XHViNzdjXHViOTdjIFx1YzgxNVx1YmNmNVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjNjI4IFx1YzgwNFx1YjgyNVx1Yzc0NCBcdWM5ZDFcdWM5MTFcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViOWU0IFx1YzIxY1x1YWMwNCBcdWM2MjRcdWM5YzEgXHVkNTVjIFx1YjA5OFx1Yjc3Y1x1YzY0MFx1YjljYyBcdWM4MDRcdWM3YzFcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIE1cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHViOTdjIFx1YzgxNVx1YmNmNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHViMmU4LCBOXHVhYzFjXHVjNzU4IFx1YjA5OFx1Yjc3YyBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVjMThkXHVhZDZkIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViNzdjIEFcdWFjMDAgXHViMDk4XHViNzdjIEJcdWM3NTggXHVjMThkXHVhZDZkXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHViMDk4XHViNzdjIEJcdWI5N2MgXHVjODE1XHViY2Y1XHVkNTU4XHViYTc0IFx1YjA5OFx1Yjc3YyBCXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWMxOGRcdWFkNmRcdWI0ZTRcdWM3NzQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1ZDU2ZFx1YmNmNVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzE4ZFx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVhY2M0XHVjZTM1IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzRcdWMxMWMsIFx1YjA5OFx1Yjc3YyBBXHVhYzAwIFx1YjA5OFx1Yjc3YyBCXHVjNzU4IFx1YzE4ZFx1YWQ2ZFx1Yzc3NFx1YWNlMCwgXHViMDk4XHViNzdjIEJcdWFjMDAgXHViMDk4XHViNzdjIENcdWM3NTggXHVjMThkXHVhZDZkXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHViMDk4XHViNzdjIENcdWI5N2MgXHVjODE1XHViY2Y1XHVkNTU4XHViYTc0IFx1YjA5OFx1Yjc3YyBBXHVjNjQwIFx1YjA5OFx1Yjc3YyBCIFx1YmFhOFx1YjQ1MCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjODE1XHViY2Y1XHVkNTU4XHViMjk0IFx1ZDZhOFx1YWNmY1x1Yjk3YyBcdWM1YmJcdWIyOTRcdWIyZTQuIFx1Yzk4OSBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMThkXHVhZDZkXHVhY2ZjLCBcdWMxOGRcdWFkNmRcdWI0ZTRcdWM3NTggXHVjMThkXHVhZDZkXHVhY2ZjLCBcdWMxOGRcdWFkNmRcdWI0ZTRcdWM3NTggXHVjMThkXHVhZDZkXHViNGU0XHVjNzU4IFx1YzE4ZFx1YWQ2ZFx1YWNmYywgLiAuIC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YmFhOFx1YjRlMCBcdWQ1NThcdWM3MDRcdWM3NTggXHViMDk4XHViNzdjXHViNGU0XHVjNzc0IFx1Yzc5MFx1YjNkOVx1YzczY1x1Yjg1YyBcdWQ1NmRcdWJjZjVcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPlx1YjA5OFx1Yjc3YyBBXHVhYzAwIFx1YjA5OFx1Yjc3YyBCXHVjNzU4IFx1YzE4ZFx1YWQ2ZFx1Yzc3NFx1YmE3NFx1YzExYyBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViMDk4XHViNzdjIENcdWM3NTggXHVjMThkXHVhZDZkXHVjNzdjIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSBcdWMxOGRcdWFkNmRcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNjI0XHVjOWMxIFx1ZDU1YyBcdWIwOThcdWI3N2NcdWM3NTggXHVjMThkXHVhZDZkXHVjNzdjIFx1YmZkMFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YjA5OFx1Yjc3YyBBLCBcdWIwOThcdWI3N2MgQiwgLi4uIFx1YjRmMSBcdWM1ZWNcdWI3ZWMgXHViMDk4XHViNzdjXHVhYzAwIFx1ZDU1YyBcdWIwOThcdWI3N2NcdWM3NTggXHVjMThkXHVhZDZkXHVjNzdjIFx1YzIxOFx1YjI5NCBcdWJiM2NcdWI4NjAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPk4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWMxOGRcdWFkNmQgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhYzAxIFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWM4MTVcdWJjZjVcdWQ1NThcdWIyOTQgXHViMzcwIFx1YjRkY1x1YjI5NCBcdWM3N2NcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0LCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIE1cdWFjMWNcdWM3NTggXHViMDk4XHViNzdjXHViOTdjIFx1YzgxNVx1YmNmNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIwOThcdWI3N2NcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSZsZTtOJmxlOzIwMClcdWFjZmMgTSgwJmxlO00mbGU7TilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjA5OFx1Yjc3Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHViYTNjXHVjODAwIFx1YjA5OFx1Yjc3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSAxMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YmU0OCBcdWNlNzggXHViNGE0XHVjNWQwIFx1Yzc3NCBcdWIwOThcdWI3N2NcdWI5N2MgXHVjODE1XHViY2Y1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjNzdjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YmU0OCBcdWNlNzhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMDk4XHViNzdjIFx1Yzc3NFx1Yjk4NFx1YjRlNFx1Yzc3NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWI0YTRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YjA5OFx1Yjc3Y1x1YjRlNFx1Yzc3NCBcdWJjMTRcdWI4NWMgXHVkNjA0XHVjN2FjIFx1YjA5OFx1Yjc3Y1x1Yzc1OCBcdWMxOGRcdWFkNmRcdWI0ZTRcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBNXHVhYzFjXHVjNzU4IFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTY4XHViOWFjIFx1YzgxNVx1YmNmNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IkNvdW50cnlCXHViOWNjIFx1YzgxNVx1YmNmNVx1ZDU1OFx1YmE3NCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgQ291bnRyeUJcdWM3NTggXHVjMThkXHVhZDZkXHVjNzc4IENvdW50cnlBXHVhYzAwIFx1YzgxNVx1YmNmNVx1YjQxOFx1YzViNCAyXHVhYzFjIFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWM4MTVcdWJjZjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMjI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJpYmluZyBGSVBBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBnb2luZyB0byBiZSBhIHZvdGluZyBhdCBGSVBBIChGZWRlcmF0aW9uIEludGVybmF0aW9uYWxlIGRlIFByb2dyYW1tYXRpb24gQXNzb2NpYXRpb24pIHRvIGRldGVybWluZSB0aGUgaG9zdCBvZiB0aGUgbmV4dCBJUFdDIChJbnRlcm5hdGlvbmFsIFByb2dyYW1taW5nIFdvcmxkIEN1cCkuIEJlbmphbWluIEJlbm5ldHQsIHRoZSBkZWxlZ2F0aW9uIG9mIERpYW1vbmRsYW5kIHRvIEZJUEEsIGlzIHRyeWluZyB0byBzZWVrIG90aGVyIGRlbGVnYXRpb24mIzM5O3Mgc3VwcG9ydCBmb3IgYSB2b3RlIGluIGZhdm9yIG9mIGhvc3RpbmcgSVBXQyBpbiBEaWFtb25kbGFuZC4gQmVuIGlzIHRyeWluZyB0byBidXkgdGhlIHZvdGVzIGJ5IGRpYW1vbmQgZ2lmdHMuIEhlIGhhcyBmaWd1cmVkIG91dCB0aGUgdm90aW5nIHByaWNlIG9mIGVhY2ggYW5kIGV2ZXJ5IGNvdW50cnkuIEhvd2V2ZXIsIGhlIGtub3dzIHRoYXQgdGhlcmUgaXMgbm8gbmVlZCB0byBkaWFtb25kLWJyaWJlIGV2ZXJ5IGNvdW50cnksIHNpbmNlIHRoZXJlIGFyZSBzbWFsbCBwb29yIGNvdW50cmllcyB0aGF0IHRha2Ugdm90ZSBvcmRlcnMgZnJvbSB0aGVpciByZXNwZWN0ZWQgc3VwZXJwb3dlcnMuIFNvLCBpZiB5b3UgYnJpYmUgYSBjb3VudHJ5LCB5b3UgaGF2ZSBnYWluZWQgdGhlIHZvdGUgb2YgYW55IG90aGVyIGNvdW50cnkgdW5kZXIgaXRzIGRvbWluYXRpb24gKGJvdGggZGlyZWN0bHkgYW5kIHZpYSBvdGhlciBjb3VudHJpZXMgZG9taW5hdGlvbikuIEZvciBleGFtcGxlLCBpZiBDIGlzIHVuZGVyIGRvbWluYXRpb24gb2YgQiwgYW5kIEIgaXMgdW5kZXIgZG9taW5hdGlvbiBvZiBBLCBvbmUgbWF5IGdldCB0aGUgdm90ZSBvZiBhbGwgdGhyZWUgY291bnRyaWVzIGp1c3QgYnkgYnJpYmluZyBBLiBOb3RlIHRoYXQgbm8gY291bnRyeSBpcyB1bmRlciBkb21pbmF0aW9uIG9mIG1vcmUgdGhhbiBvbmUgY291bnRyeSwgYW5kIHRoZSBkb21pbmF0aW9uIHJlbGF0aW9uc2hpcCBtYWtlcyBubyBjeWNsZS4gWW91IGFyZSB0byBoZWxwIGhpbSwgYWdhaW5zdCBhIGJpZyBkaWFtb25kLCBieSB3cml0aW5nIGEgcHJvZ3JhbSB0byBmaW5kIG91dCB0aGUgbWluaW11bSBudW1iZXIgb2YgZGlhbW9uZHMgbmVlZGVkIHN1Y2ggdGhhdCBhdCBsZWFzdCBtIGNvdW50cmllcyB2b3RlIGluIGZhdm9yIG9mIERpYW1vbmRsYW5kLiBTaW5jZSBEaWFtb25kbGFuZCBpcyBhIGNhbmRpZGF0ZSwgaXQgc3RhbmRzIG91dCBvZiB0aGUgdm90aW5nIHByb2Nlc3MuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBuICgxICZsZTsgbiAmbGU7IDIwMCkgYW5kIG0gKDAgJmxlOyBtICZsZTsgbikgd2hpY2ggYXJlIHRoZSBudW1iZXIgb2YgY291bnRyaWVzIHBhcnRpY2lwYXRpbmcgaW4gdGhlIHZvdGluZyBwcm9jZXNzLCBhbmQgdGhlIG51bWJlciBvZiB2b3RlcyBEaWFtb25kbGFuZCBuZWVkcy4gVGhlIG5leHQgbiBsaW5lcywgZWFjaCBkZXNjcmliaW5nIG9uZSBjb3VudHJ5LCBhcmUgb2YgdGhlIGZvbGxvd2luZyBmb3JtOjxcL3A+XHJcblxyXG48cD5Db3VudHJ5TmFtZSBEaWFtb25kQ291bnQgRENOYW1lPHN1Yj4xPFwvc3ViPiBEQ05hbWU8c3ViPjI8XC9zdWI+Li4uPFwvcD5cclxuXHJcbjxwPkNvdW50cnlOYW1lICwgdGhlIG5hbWUgb2YgdGhlIGNvdW50cnksIGlzIGEgc3RyaW5nIG9mIGF0IGxlYXN0IG9uZSBhbmQgYXQgbW9zdCAxMDAgbGV0dGVycyBhbmQgRGlhbW9uZENvdW50IGlzIGEgcG9zaXRpdmUgaW50ZWdlciB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRpYW1vbmRzIG5lZWRlZCB0byBnZXQgdGhlIHZvdGUgb2YgdGhhdCBjb3VudHJ5IGFuZCBhbGwgb2YgdGhlIGNvdW50cmllcyB0aGF0IHRoZWlyIG5hbWVzIGNvbWUgaW4gdGhlIGxpc3QgRENOYW1lPHN1Yj4xPFwvc3ViPiBEQ05hbWU8c3ViPjI8XC9zdWI+Li4uIHdoaWNoIG1lYW5zIHRoZXkgYXJlIHVuZGVyIGRpcmVjdCBkb21pbmF0aW9uIG9mIHRoYXQgY291bnRyeS4gTm90ZSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRoYXQgc29tZSBjb3VudHJpZXMgZG8gbm90IGhhdmUgYW55IG90aGVyIGNvdW50cnkgdW5kZXIgZG9taW5hdGlvbi4gVGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgbWFya2VkIGJ5IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSAjIGNoYXJhY3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIG51bWJlciBzaG93aW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkaWFtb25kcyBuZWVkZWQgdG8gZ2FpbiB0aGUgdm90ZSBvZiBhdCBsZWFzdCBtIGNvdW50cmllcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2006 G번

  • 문제를 번역한 사람: author5