시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB148344471239227.225%

문제

농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.

두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.

  +---5---+---3---+    ->    +---3---+

게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.

주어진 파이프들의 맵으로부터 우물(A)와 외양간(Z) 사이의 유량을 결정하라.

각 노드의 이름은 알파벳으로 지어져 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

파이프 BC와 CD는 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

그러면 BD와 DZ 역시 합쳐질 수 있다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

병렬 연결된 BZ 역시 합쳐진다.

                 B
        A+---3---+---9---+Z

그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.

        A+---3---+Z

한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.

i번째 파이프는 두개의 다른 노드 ai와 bi와 연결돼 있고 Fi (1 ≤ Fi ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.

출력

첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.

예제 입력 1

5
A B 3
B C 3
C D 5
D Z 4
B Z 6

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjYwODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVjNzIwXHViN2M5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWMwYWNcdWFmYmMgXHVjODc0XHVjNzQwIFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWNkYTlcdWJkODRcdWQ1NWMgXHViYjNjXHVjNzQ0IFx1YjljOFx1YzJkY1x1YWUzOCBcdWM2ZDBcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWIxOGRcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjNmIwXHViYjNjXHVjNWQwXHVjMTFjIFx1YzY3OFx1YzU5MVx1YWMwNFx1Yzc0NCBcdWM3ODdcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWM3NTggXHVjOWMwXHViM2M0XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1Yzg3NFx1Yzc0MCBcdWM1NDRcdWM4ZmMgXHViMmU0XHVjNTkxXHVkNTVjIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWI0ZTRcdWM3NzQgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YzZiMFx1YzVmMFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViM2ZjXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YzU0Y1x1YzU1OFx1YjJlNC4gXHVjODc0XHVjNzQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTQgXHVjNzIwXHViN2M5XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWJjMzBcdWMyMThcdWFkMDBcdWM3NzQgXHVkNTVjXHVjOTA0XHViODVjIFx1YzVmMFx1YWNiMCBcdWIzZmMgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWI0NTAgXHVhZDAwXHVjNzU4IFx1YzcyMFx1YjdjOSBcdWM5MTEgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzNjXHViODVjIFx1ZDc1MFx1Yjk3NFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNmE5XHViN2M5XHVjNzc0IDVcdWM3NzggXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIFx1YzZhOVx1YjdjOVx1Yzc3NCAzXHVjNzc4IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWJhNzQgXHVkNTVjXHVhYzFjXHVjNzU4IFx1YzZhOVx1YjdjOSAzXHVjOWRjXHViOWFjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgKy0tLTUtLS0rLS0tMy0tLSsgICAgLSZndDsgICAgKy0tLTMtLS0rPFwvcHJlPlxyXG5cclxuPHA+XHVhYzhjXHViMmU0XHVhYzAwLCBcdWJjZDFcdWI4MmNcdWI4NWMgXHVjNWYwXHVhY2IwXHViM2ZjIFx1Yzc4OFx1YjI5NCBcdWJjMzBcdWMyMThcdWFkMDBcdWI0ZTRcdWM3NDAgXHVhYzAxIFx1YzZhOVx1YjdjOVx1Yzc1OCBcdWQ1NjlcdWI5Y2NcdWQwN2NcdWM3NTggXHViYjNjXHVjNzQ0IFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgKy0tLTUtLS0rXHJcbiAtLS0rICAgICAgICstLS0gICAgLSZndDsgICAgKy0tLTgtLS0rXHJcbiAgICArLS0tMy0tLStcclxuPFwvcHJlPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWM1YjRcdWI1YTQgXHVhYzgzXHVjNWQwXHViM2M0IFx1YzVmMFx1YWNiMFx1YjNmYyBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWJiM2NcdWM3NDQgXHVkNzUwXHViOTc0XHVhYzhjIFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWJiYzBcdWI4NWMgXHVjODFjXHVhYzcwXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgKy0tLTUtLS0rXHJcbiAtLS0rICAgICAgICAgICAgICAgLSZndDsgICAgKy0tLTMtLS0rXHJcbiAgICArLS0tMy0tLSstLVxyXG48XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YmNmNVx1YzdhMVx1ZDU1OFx1YWM4YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYWE4XHViNGUwIFx1YmMzMFx1YzIxOFx1YWQwMFx1YjRlNFx1Yzc0MCBcdWQ1NWNcdWFjMWNcdWM3NTggXHVjZDVjXHViMzAwIFx1YzcyMFx1YjdjOVx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViYzMwXHVjMjE4XHVhZDAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjRlNFx1Yzc1OCBcdWI5ZjVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjNmIwXHViYjNjKEEpXHVjNjQwIFx1YzY3OFx1YzU5MVx1YWMwNChaKSBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNzIwXHViN2M5XHVjNzQ0IFx1YWNiMFx1YzgxNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1YzljMFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgKy0tLS0tLS0tLS0tNi0tLS0tLS0tLS0tK1xyXG4gICAgICAgIEErLS0tMy0tLStCICAgICAgICAgICAgICAgICAgICAgICtaXHJcbiAgICAgICAgICAgICAgICAgKy0tLTMtLS0rLS0tNS0tLSstLS00LS0tK1xyXG4gICAgICAgICAgICAgICAgICAgICAgICAgQyAgICAgICBEXHJcbjxcL3ByZT5cclxuXHJcbjxwPlx1ZDMwY1x1Yzc3NFx1ZDUwNCBCQ1x1YzY0MCBDRFx1YjI5NCBcdWQ1NjlcdWNjZDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS02LS0tLS0tLS0tLS0rXHJcbiAgICAgICAgQSstLS0zLS0tK0IgICAgICAgICAgICAgICAgICAgICAgK1pcclxuICAgICAgICAgICAgICAgICArLS0tLS0zLS0tLS0rLS0tLS00LS0tLS0rXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRFxyXG48XC9wcmU+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWJhNzQgQkRcdWM2NDAgRFogXHVjNWVkXHVjMmRjIFx1ZDU2OVx1Y2NkMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICstLS0tLS0tLS0tLTYtLS0tLS0tLS0tLStcclxuICAgICAgICBBKy0tLTMtLS0rQiAgICAgICAgICAgICAgICAgICAgICArWlxyXG4gICAgICAgICAgICAgICAgICstLS0tLS0tLS0tLTMtLS0tLS0tLS0tLStcclxuPFwvcHJlPlxyXG5cclxuPHA+XHViY2QxXHViODJjIFx1YzVmMFx1YWNiMFx1YjQxYyBCWiBcdWM1ZWRcdWMyZGMgXHVkNTY5XHVjY2QwXHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgIEJcclxuICAgICAgICBBKy0tLTMtLS0rLS0tOS0tLStaXHJcbjxcL3ByZT5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1YmE3NCBBQlx1YzY0MCBCWiBcdWM1ZWRcdWMyZGMgXHVkNTY5XHVjY2QwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWFjZTAgXHVjNmE5XHViN2M5IDNcdWM3NzggXHViYzMwXHVjMjE4XHVhZDAwIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgQSstLS0zLS0tK1o8XC9wcmU+XHJcblxyXG48cD5cdWQ1NWMgXHVkMzBjXHVjNzc0XHVkNTA0XHViNGU0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWM3N2RcdWFjZTAuIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWM0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWIxOTNcdWM3NDAgXHViNGE0IEFcdWJkODBcdWQxMzAgWlx1YWU0Y1x1YzljMCBcdWQ3NTBcdWI5NzRcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzcyMFx1YjdjOVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWI3N2MuIFx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI0ZTRcdWM3NDAgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM4MDFcdWM2YTlcdWMyZGNcdWNmMWMgXHVjOTA0XHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVkMzBjXHVjNzc0XHVkNTA0XHViMjk0IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHViMTc4XHViNGRjIGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzVmMFx1YWNiMFx1YjNmYyBcdWM3ODhcdWFjZTAgRjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBGPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM3MjBcdWI3YzlcdWM3NDQgXHVhYzE2XHViMjk0XHViMmU0LiBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDAgXHVhYzE5XHVjOWMwXHViOWNjLCBcdWIzMDBcdWMxOGNcdWJiMzhcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNzUwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDcwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjgsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWM3NzRcdWI5ODQoXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MCBcdWI2MTBcdWIyOTQgXHVjMThjXHViYjM4XHVjNzkwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgQVx1YzVkMFx1YzExYyBaXHVhZTRjXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWM3MjBcdWI3YzlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYwODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUb3RhbCBGbG93IiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBhbHdheXMgd2FudHMgaGlzIGNvd3MgdG8gaGF2ZSBlbm91Z2ggd2F0ZXIgYW5kIHRodXMgaGFzIG1hZGUgYSBtYXAgb2YgdGhlIE4gKDEgJmx0Oz0gTiAmbHQ7PSA3MDApIHdhdGVyIHBpcGVzIG9uIHRoZSBmYXJtIHRoYXQgY29ubmVjdCB0aGUgd2VsbCB0byB0aGUgYmFybi4gSGUgd2FzIHN1cnByaXNlZCB0byBmaW5kIGEgd2lsZCBtZXNzIG9mIGRpZmZlcmVudCBzaXplIHBpcGVzIGNvbm5lY3RlZCBpbiBhbiBhcHBhcmVudGx5IGhhcGhhemFyZCB3YXkuIEhlIHdhbnRzIHRvIGNhbGN1bGF0ZSB0aGUgZmxvdyB0aHJvdWdoIHRoZSBwaXBlcy48XC9wPlxyXG5cclxuPHA+VHdvIHBpcGVzIGNvbm5lY3RlZCBpbiBhIHJvdyBhbGxvdyB3YXRlciBmbG93IHRoYXQgaXMgdGhlIG1pbmltdW0gb2YgdGhlIHZhbHVlcyBvZiB0aGUgdHdvIHBpcGUmIzM5O3MgZmxvdyB2YWx1ZXMuIFRoZSBleGFtcGxlIG9mIGEgcGlwZSB3aXRoIGZsb3cgY2FwYWNpdHkgNSBjb25uZWN0aW5nIHRvIGEgcGlwZSBvZiBmbG93IGNhcGFjaXR5IDMgY2FuIGJlIHJlZHVjZWQgbG9naWNhbGx5IHRvIGEgc2luZ2xlIHBpcGUgb2YgZmxvdyBjYXBhY2l0eSAzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICstLS01LS0tKy0tLTMtLS0rICAgIC0mZ3Q7ICAgICstLS0zLS0tK1xyXG48XC9wcmU+XHJcblxyXG48cD5TaW1pbGFybHksIHBpcGVzIGluIHBhcmFsbGVsIGxldCB0aHJvdWdoIHdhdGVyIHRoYXQgaXMgdGhlIHN1bSBvZiB0aGVpciBmbG93IGNhcGFjaXRpZXM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICArLS0tNS0tLStcclxuIC0tLSsgICAgICAgKy0tLSAgICAtJmd0OyAgICArLS0tOC0tLStcclxuICAgICstLS0zLS0tK1xyXG48XC9wcmU+XHJcblxyXG48cD5GaW5hbGx5LCBhIHBpcGUgdGhhdCBjb25uZWN0cyB0byBub3RoaW5nIGVsc2UgY2FuIGJlIHJlbW92ZWQ7IGl0IGNvbnRyaWJ1dGVzIG5vIGZsb3cgdG8gdGhlIGZpbmFsIG92ZXJhbGwgY2FwYWNpdHk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICArLS0tNS0tLStcclxuIC0tLSsgICAgICAgICAgICAgICAtJmd0OyAgICArLS0tMy0tLStcclxuICAgICstLS0zLS0tKy0tXHJcbjxcL3ByZT5cclxuXHJcbjxwPkFsbCB0aGUgcGlwZXMgaW4gdGhlIG1hbnkgbWF6ZXMgb2YgcGx1bWJpbmcgY2FuIGJlIHJlZHVjZWQgdXNpbmcgdGhlc2UgaWRlYXMgaW50byBhIHNpbmdsZSB0b3RhbCBmbG93IGNhcGFjaXR5LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIG1hcCBvZiB0aGUgcGlwZXMsIGRldGVybWluZSB0aGUgZmxvdyBjYXBhY2l0eSBiZXR3ZWVuIHRoZSB3ZWxsIChBKSBhbmQgdGhlIGJhcm4gKFopLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGlzIGV4YW1wbGUgd2hlcmUgbm9kZSBuYW1lcyBhcmUgbGFiZWxlZCB3aXRoIGxldHRlcnM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgKy0tLS0tLS0tLS0tNi0tLS0tLS0tLS0tK1xyXG4gICAgICAgIEErLS0tMy0tLStCICAgICAgICAgICAgICAgICAgICAgICtaXHJcbiAgICAgICAgICAgICAgICAgKy0tLTMtLS0rLS0tNS0tLSstLS00LS0tK1xyXG4gICAgICAgICAgICAgICAgICAgICAgICAgQyAgICAgICBEXHJcbjxcL3ByZT5cclxuXHJcbjxwPlBpcGUgQkMgYW5kIENEIGNhbiBiZSBjb21iaW5lZDo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICArLS0tLS0tLS0tLS02LS0tLS0tLS0tLS0rXHJcbiAgICAgICAgQSstLS0zLS0tK0IgICAgICAgICAgICAgICAgICAgICAgK1pcclxuICAgICAgICAgICAgICAgICArLS0tLS0zLS0tLS0rLS0tLS00LS0tLS0rXHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRFxyXG48XC9wcmU+XHJcblxyXG48cD5UaGVuIEJEIGFuZCBEWiBjYW4gYmUgY29tYmluZWQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgKy0tLS0tLS0tLS0tNi0tLS0tLS0tLS0tK1xyXG4gICAgICAgIEErLS0tMy0tLStCICAgICAgICAgICAgICAgICAgICAgICtaXHJcbiAgICAgICAgICAgICAgICAgKy0tLS0tLS0tLS0tMy0tLS0tLS0tLS0tK1xyXG48XC9wcmU+XHJcblxyXG48cD5UaGVuIHR3byBsZWdzIG9mIEJaIGNhbiBiZSBjb21iaW5lZDo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICBCXHJcbiAgICAgICAgQSstLS0zLS0tKy0tLTktLS0rWlxyXG48XC9wcmU+XHJcblxyXG48cD5UaGVuIEFCIGFuZCBCWiBjYW4gYmUgY29tYmluZWQgdG8geWllbGQgYSBuZXQgY2FwYWNpdHkgb2YgMzo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICBBKy0tLTMtLS0rWlxyXG48XC9wcmU+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gcmVhZCBpbiBhIHNldCBvZiBwaXBlcyBkZXNjcmliZWQgYXMgdHdvIGVuZHBvaW50cyBhbmQgdGhlbiBjYWxjdWxhdGUgdGhlIG5ldCBmbG93IGNhcGFjaXR5IGZyb20gJiMzOTtBJiMzOTsgdG8gJiMzOTtaJiMzOTsuIEFsbCBuZXR3b3JrcyBpbiB0aGUgdGVzdCBkYXRhIGNhbiBiZSByZWR1Y2VkIHVzaW5nIHRoZSBydWxlcyBoZXJlLjxcL3A+XHJcblxyXG48cD5QaXBlIGkgY29ubmVjdHMgdHdvIGRpZmZlcmVudCBub2RlcyBhX2kgYW5kIGJfaSAoYV9pIGluIHJhbmdlICYjMzk7QS1aYS16JiMzOTs7IGJfaSBpbiByYW5nZSAmIzM5O0EtWmEteiYjMzk7KSBhbmQgaGFzIGZsb3cgRl9pICgxICZsdDs9IEZfaSAmbHQ7PSAxLDAwMCkuIE5vdGUgdGhhdCBsb3dlci0gYW5kIHVwcGVyLWNhc2Ugbm9kZSBuYW1lcyBhcmUgaW50ZW5kZWQgdG8gYmUgdHJlYXRlZCBhcyBkaWZmZXJlbnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OICsgMTogTGluZSBpKzEgZGVzY3JpYmVzIHBpcGUgaSB3aXRoIHR3byBsZXR0ZXJzIGFuZCBhbiBpbnRlZ2VyLCBhbGwgc3BhY2Utc2VwYXJhdGVkOiBhX2ksIGJfaSwgYW5kIEZfaTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCB0aGUgbWF4aW11bSBmbG93IGZyb20gdGhlIHdlbGwgKCYjMzk7QSYjMzk7KSB0byB0aGUgYmFybiAoJiMzOTtaJiMzOTspPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO January 2009 Contest > Silver 2번