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

문제

상근이는 사다리 게임을 하고 있다. 사다리는 n개의 세로줄과 m개의 막대로 이루어져 있다. 세로줄은 왼쪽에서 오른쪽으로 1부터 n까지 번호가 붙어있다. 세로줄 i의 아래에는 양의 정수 si가 적혀있다.

세로줄 i의 상단부터 순서대로 길을 따라가게 되고, 하단에 적혀있는 정수가 그 막대기 i를 선택할 때 얻는 정수이다. 예를 들어, 위의 그림에서 세로줄 1을 선택하면 80점을 얻게 되고, 2를 선택하면 100점을 얻게 된다.

상근이는 세로줄 1부터 세로줄 k까지 연속된 세로줄 k개를 선택한다. 그리고, 선택한 세로줄의 점수의 합계가 상근이의 점수가 된다. 상근이는 막대를 최대 한 개 지울 수 있다. 만약, 막대를 하나 제거한다면, 제거하고 난 이후에 사다리를 타야 한다.

입력으로 사다리의 모양과 선택한 세로줄의 수 k가 주어진다. 이때, 상근이가 얻을 수 있는 가장 작은 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로줄의 개수 n(2 ≤ n ≤ 1000), 막대의 개수 m(1 ≤ m ≤ 100000), 막대의 길이 h(2 ≤ h ≤ 1000), 상근이가 선택한 세로줄의 수 k(1 ≤ k ≤ n)가 주어진다.

다음 n개 줄에는 세로 막대의 하단에 적혀있는 점수 si가 주어진다. (s1 + s2 + ... + sn ≤ 2×109)

다음 m개 줄에는 막대 i의 위치를 나타내는 ai와 bi가 주어진다. (1 ≤ ai ≤ n-1, 1 ≤ bi ≤ h-1) 막대 i는 세로줄 ai와 ai+1을 연결하고, 상단으로부터의 거리가 bi이다.

출력

첫째 줄에 상근이가 얻을 수 있는 최소 점수를 출력한다.

예제 입력 1

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

예제 출력 1

100

예제 입력 2

2 2 5 1
10
20
1 1
1 3

예제 출력 2

10

W3sicHJvYmxlbV9pZCI6IjU1NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWIyZTRcdWI5YWMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGFjXHViMmU0XHViOWFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWIyZTRcdWI5YWNcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWMxMzhcdWI4NWNcdWM5MDRcdWFjZmMgbVx1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMTM4XHViODVjXHVjOTA0XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzEzOFx1Yjg1Y1x1YzkwNCBpXHVjNzU4IFx1YzU0NFx1Yjc5OFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IHNpXHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4XHViODVjXHVjOTA0IGlcdWM3NTggXHVjMGMxXHViMmU4XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFlMzhcdWM3NDQgXHViNTMwXHViNzdjXHVhYzAwXHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVkNTU4XHViMmU4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhZGY4IFx1YjljOVx1YjMwMFx1YWUzMCBpXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWI1NGMgXHVjNWJiXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWMxMzhcdWI4NWNcdWM5MDQgMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgODBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxOFx1YWNlMCwgMlx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgMTAwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMzhcdWI4NWNcdWM5MDQgMVx1YmQ4MFx1ZDEzMCBcdWMxMzhcdWI4NWNcdWM5MDQga1x1YWU0Y1x1YzljMCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjMTM4XHViODVjXHVjOTA0IGtcdWFjMWNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMzhcdWI4NWNcdWM5MDRcdWM3NTggXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YWNjNFx1YWMwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxYyBcdWM5YzBcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwIFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMGFjXHViMmU0XHViOWFjXHViOTdjIFx1ZDBjMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWMwYWNcdWIyZTRcdWI5YWNcdWM3NTggXHViYWE4XHVjNTkxXHVhY2ZjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMzhcdWI4NWNcdWM5MDRcdWM3NTggXHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTM4XHViODVjXHVjOTA0XHVjNzU4IFx1YWMxY1x1YzIxOCBuKDIgJmxlOyBuICZsZTsgMTAwMCksIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFjMWNcdWMyMTggbSgxICZsZTsgbSAmbGU7IDEwMDAwMCksIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzQgaCgyICZsZTsgaCAmbGU7IDEwMDApLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzEzOFx1Yjg1Y1x1YzkwNFx1Yzc1OCBcdWMyMTggaygxICZsZTsgayAmbGU7IG4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOFx1Yjg1YyBcdWI5YzlcdWIzMDBcdWM3NTggXHVkNTU4XHViMmU4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMTggczxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoczxzdWI+MTxcL3N1Yj4gKyBzPHN1Yj4yPFwvc3ViPiArIC4uLiArIHM8c3ViPm48XC9zdWI+ICZsZTsgMiZ0aW1lczsxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzlcdWIzMDAgaVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IG4tMSwgMSAmbGU7IGI8c3ViPmk8XC9zdWI+ICZsZTsgaC0xKSBcdWI5YzlcdWIzMDAgaVx1YjI5NCBcdWMxMzhcdWI4NWNcdWM5MDQgYTxzdWI+aTxcL3N1Yj5cdWM2NDAgYTxzdWI+aTxcL3N1Yj4rMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAsIFx1YzBjMVx1YjJlOFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgYjxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDcwYmU3NGItZGIxNS00Yjk1LTk2ZTgtMmUyY2Y1ZTFjMDViXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxNTZweDsgaGVpZ2h0OiAyNTdweDtcIiBcLz48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80ZTk0MzBmMC1lODYyLTQyN2EtYjJjNS03ZDBkMDUwNjc0YTJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDY3cHg7IGhlaWdodDogMTk5cHg7XCIgXC8+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNTU3MiIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzA0Mlx1MzA3Zlx1MzA2MFx1MzA0Zlx1MzA1OCIsImRlc2NyaXB0aW9uIjoiPHA+XHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmIEogXHU1NDFiXHUzMDY4XHU0ZTAwXHU3ZGQyXHUzMDZiXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDkyXHU0ZjdmXHUzMDYzXHUzMDY2XHU5MDRhXHUzMDkzXHUzMDY3XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDZmIG4gXHU2NzJjXHUzMDZlXHU3ZTI2XHU2OGQyXHUzMDY4bSBcdTY3MmNcdTMwNmVcdTZhMmFcdTY4ZDJcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGVcdTdlMjZcdTY4ZDJcdTMwNmJcdTMwNmZcdTVkZTZcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmIgMSBcdTMwNGJcdTMwODkgbiBcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTMwNjRcdTMwNDRcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTdlMjZcdTY4ZDIgaSBcdTMwNmVcdTRlMGJcdTdhZWZcdTMwNmJcdTMwNmZcdTZiNjNcdTY1NzRcdTY1NzAgczxzdWI+aTxcL3N1Yj4gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZTQ2ODc4M2ItMDlkYS00MzQwLWJjM2MtOTkxOWE5MzcxYTNkXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxNTZweDsgaGVpZ2h0OiAyNTJweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHU1NmYzIDMtMSBcdTMwNDJcdTMwN2ZcdTMwNjBcdTMwNGZcdTMwNThcdTMwNmVcdTRmOGJcdWZmMDhuID0gNCwgbSA9IDUsIHM8c3ViPjE8XC9zdWI+ID0gMjAsIHM8c3ViPjI8XC9zdWI+ID0gODAsIHM8c3ViPjM8XC9zdWI+ID0gMTAwLCBzPHN1Yj40PFwvc3ViPiA9IDUwXHVmZjA5PFwvcD5cclxuXHJcbjxwPlx1N2UyNlx1NjhkMiBpIFx1MzA2ZVx1NGUwMFx1NzU2YVx1NGUwYVx1MzA0Ylx1MzA4OVx1OTgwNlx1MzA2Ylx1OTA1M1x1MzA5Mlx1MzA1Zlx1MzA2OVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA0ZFx1NTIzMFx1OTA1NFx1MzA1N1x1MzA1Zlx1NGUwYlx1N2FlZlx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1NjU3NFx1NjU3MFx1MzA0Y1x1ZmYwY1x1N2UyNlx1NjhkMiBpIFx1MzA5Mlx1OTA3OFx1MzA5M1x1MzA2MFx1NTgzNFx1NTQwOFx1MzA2ZVx1NWY5N1x1NzBiOVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1NGY4Ylx1MzA0OFx1MzA3MFx1ZmYwY1x1NTZmMyAzLTEgXHUzMDY3XHUzMDZmXHVmZjBjXHU3ZTI2XHU2OGQyIDEgXHUzMDkyXHU5MDc4XHUzMDc2XHUzMDY4XHU1Zjk3XHU3MGI5XHUzMDZmIDgwIFx1NzBiOVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1N2UyNlx1NjhkMiAyIFx1MzA5Mlx1OTA3OFx1MzA3Nlx1MzA2OFx1NWY5N1x1NzBiOVx1MzA2ZiAxMDAgXHU3MGI5XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMmYxMGQxNmQtOWUzNS00MTAxLWIxMzAtMzA3OGZlMmM3N2U0XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzODhweDsgaGVpZ2h0OiAyNTJweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHU1NmYzIDMtMiBcdTkwNTNcdTMwNmVcdTMwNWZcdTMwNjlcdTMwOGFcdTY1YjlcdTMwNmVcdTRmOGI8XC9wPlxyXG5cclxuPHA+SiBcdTU0MWJcdTMwNmZcdTdlMjZcdTY4ZDIgMSBcdTMwNGJcdTMwODlcdTdlMjZcdTY4ZDIgayBcdTMwN2VcdTMwNjdcdTMwNmVcdTkwMjNcdTdkOWFcdTMwNTdcdTMwNWYgayBcdTY3MmNcdTMwOTJcdTkwNzhcdTMwNzZcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNTdcdTMwNWZcdWZmMGVcdTMwNWRcdTMwOGNcdTMwODkgayBcdTY3MmNcdTMwNmVcdTdlMjZcdTY4ZDJcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjBcdTMwNjhcdTMwNGRcdTMwNmVcdTcwYjlcdTY1NzBcdTMwNmVcdTU0MDhcdThhMDhcdTMwNGMgSiBcdTU0MWJcdTMwNmVcdTVmOTdcdTcwYjlcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTMwNDJcdTMwN2ZcdTMwNjBcdTMwNGZcdTMwNThcdTUxODVcdTMwNmVcdTZhMmFcdTY4ZDJcdTMwOTJcdTRlMDBcdTY3MmNcdTkwNzhcdTMwNzNcdWZmMGNcdTMwNWRcdTMwNmVcdTZhMmFcdTY4ZDJcdTMwOTJcdTMwNDJcdTMwN2ZcdTMwNjBcdTMwNGZcdTMwNThcdTMwNGJcdTMwODlcdTUyNGFcdTk2NjRcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGVcdWZmMDhcdTUyNGFcdTk2NjRcdTMwNTdcdTMwNmFcdTMwNGZcdTMwNjZcdTMwODJcdTMwODhcdTMwNDRcdWZmMGVcdWZmMDlcdTMwODJcdTMwNTdcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNGNcdTZhMmFcdTY4ZDJcdTMwOTJcdTRlMDBcdTY3MmNcdTUyNGFcdTk2NjRcdTMwNTdcdTMwNWZcdTU4MzRcdTU0MDhcdTMwNmZcdWZmMGNcdTUyNGFcdTk2NjRcdTVmOGNcdTMwNmVcdTMwNDJcdTMwN2ZcdTMwNjBcdTMwNGZcdTMwNThcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdWZmMGNcdTdlMjZcdTY4ZDIgMSBcdTMwNGJcdTMwODlcdTdlMjZcdTY4ZDIgayBcdTMwN2VcdTMwNjdcdTMwNmVcdTkwMjNcdTdkOWFcdTMwNTdcdTMwNWYgayBcdTY3MmNcdTMwNmVcdTdlMjZcdTY4ZDJcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjBcdTMwNjhcdTMwNGRcdTMwNmVcdTcwYjlcdTY1NzBcdTMwNmVcdTU0MDhcdThhMDhcdTMwNGMgSiBcdTU0MWJcdTMwNmVcdTVmOTdcdTcwYjlcdTMwNjhcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2XHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDZlXHU1ZjYyXHUzMDY4IEogXHU1NDFiXHUzMDZlXHU5MDc4XHUzMDc2XHU3ZTI2XHU2OGQyXHUzMDZlXHU2NzJjXHU2NTcwIGsgXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjSiBcdTU0MWJcdTMwNmVcdTVmOTdcdTcwYjlcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmIDQgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIG4sIG0sIGgsIGsgXHUzMDRjXHU3YTdhXHU3NjdkXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY3XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlbiAoMiAmbGU7IG4gJmxlOyAxMDAwKSBcdTMwNmZcdTdlMjZcdTY4ZDJcdTMwNmVcdTY3MmNcdTY1NzBcdTMwOTJcdWZmMGNtICgxICZsZTsgbSAmbGU7IDEwMDAwMCkgXHUzMDZmXHU2YTJhXHU2OGQyXHUzMDZlXHU2NzJjXHU2NTcwXHUzMDkyXHVmZjBjaCAoMiAmbGU7IGggJmxlOyAxMDAwKSBcdTMwNmZcdTdlMjZcdTY4ZDJcdTMwNmVcdTk1NzdcdTMwNTVcdTMwOTJcdWZmMGNrICgxICZsZTsgayAmbGU7IG4pIFx1MzA2ZiBKIFx1NTQxYlx1MzA0Y1x1OTA3OFx1MzA3Nlx1N2UyNlx1NjhkMlx1MzA2ZVx1NjcyY1x1NjU3MFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTdkOWFcdTMwNGYgbiBcdTg4NGNcdTMwNmJcdTMwNmZcdTdlMjZcdTY4ZDJcdTMwNmVcdTRlMGJcdTdhZWZcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTcwYjlcdTY1NzBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVpKzEgXHU4ODRjXHU3NmVlICgxICZsZTsgaSAmbGU7IG4pXHUzMDZiXHUzMDZmXHU2YjYzXHU2NTc0XHU2NTcwIHM8c3ViPmk8XC9zdWI+IFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY3M8c3ViPjE8XC9zdWI+ICsgczxzdWI+MjxcL3N1Yj4gKyAmbWlkZG90OyAmbWlkZG90OyAmbWlkZG90OyArIHM8c3ViPm48XC9zdWI+ICZsZTsgMjAwMDAwMDAwMCA9IDIgJnRpbWVzOyAxMDxzdXA+OTxcL3N1cD4gXHUzMDkyXHU2ZTgwXHUzMDVmXHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1N2Q5YVx1MzA0ZiBtIFx1ODg0Y1x1MzA2Ylx1MzA2Zlx1NmEyYVx1NjhkMlx1MzA2ZVx1NGY0ZFx1N2Y2ZVx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1NmEyYVx1NjhkMlx1MzA2Ylx1MzA2ZiAxIFx1MzA0Ylx1MzA4OSBtIFx1MzA3ZVx1MzA2N1x1MzA2ZVx1NzU2YVx1NTNmN1x1MzA0Y1x1MzA2NFx1MzA0NFx1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZWkgKyBuICsgMSBcdTg4NGNcdTc2ZWUgKDEgJmxlOyBpICZsZTsgbSkgXHUzMDZiXHUzMDZmXHVmZjBjXHU2YTJhXHU2OGQyIGkgXHUzMDZlXHU0ZjRkXHU3ZjZlXHUzMDkyXHU4ODY4XHUzMDU5IDIgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPigxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBuICZtaW51czsgMSwgMSAmbGU7IGI8c3ViPmk8XC9zdWI+ICZsZTsgaCAmbWludXM7IDEpIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2N1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY1x1NmEyYVx1NjhkMiBpIFx1MzA0Y1x1N2UyNlx1NjhkMiBhPHN1Yj5pPFwvc3ViPiBcdTMwNjhcdTdlMjZcdTY4ZDIgYTxzdWI+aTxcL3N1Yj4gKyAxIFx1MzA5Mlx1N2Q1MFx1MzA3M1x1ZmYwY1x1NmEyYVx1NjhkMiBpIFx1MzA2ZVx1NGUwYVx1N2FlZlx1MzA0Ylx1MzA4OVx1MzA2ZVx1OGRkZFx1OTZlMlx1MzA0YyBiPHN1Yj5pPFwvc3ViPiBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTMwNjlcdTMwNmUgMlx1MzA2NFx1MzA2ZVx1NmEyYVx1NjhkMlx1MzA4Mlx1N2FlZlx1NzBiOVx1MzA5Mlx1NTE3MVx1NjcwOVx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1NTFmYVx1NTI5Ylx1MzA2ZkogXHU1NDFiXHUzMDZlXHU1Zjk3XHU3MGI5XHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDZlXHUzMDdmXHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlx1NGY4YiAxIFx1MzA2Zlx1NTZmMyAzLTEgXHUzMDZiXHU1YmZlXHU1ZmRjXHUzMDU3XHVmZjBjXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHU2YTJhXHU2OGQyIDQgXHVmZjA4XHU3ZTI2XHU2OGQyIDEgXHUzMDY4XHU3ZTI2XHU2OGQyIDIgXHUzMDkyXHU0ZTBhXHU3YWVmXHUzMDRiXHUzMDg5XHU4ZGRkXHU5NmUyIDUgXHUzMDZlXHU1ODM0IFx1NjI0MFx1MzA2N1x1N2Q1MFx1MzA3Nlx1NmEyYVx1NjhkMlx1ZmYwOVx1MzA5Mlx1NTI0YVx1OTY2NFx1MzA1N1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY0ogXHU1NDFiXHUzMDZlXHU1Zjk3XHU3MGI5XHUzMDZmXHU2NzAwXHU1YzBmXHUzMDZiXHUzMDZhXHUzMDhiXHVmZjBlXHU0ZjhiIDIgXHUzMDY3XHUzMDZmXHVmZjBjXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHU2YTJhXHU2OGQyIFx1MzA5Mlx1NTI0YVx1OTY2NFx1MzA1N1x1MzA2YVx1MzA0NFx1NTgzNFx1NTQwOFx1MzA2YiBKIFx1NTQxYlx1MzA2ZVx1NWY5N1x1NzBiOVx1MzA0Y1x1NjcwMFx1NWMwZlx1MzA2Ylx1MzA2YVx1MzA4Ylx1ZmYwZVx1ZmYwOFx1NTZmMyAzLTMgXHUzMDkyXHU4OThiXHUzMDg4XHVmZjBlXHVmZjA5PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlciB0ZC1taWRkbGVcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUwJTtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2Q3MGJlNzRiLWRiMTUtNGI5NS05NmU4LTJlMmNmNWUxYzA1YlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTU2cHg7IGhlaWdodDogMjU3cHg7XCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUwJTtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzRlOTQzMGYwLWU4NjItNDI3YS1iMmM1LTdkMGQwNTA2NzRhMlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjdweDsgaGVpZ2h0OiAxOTlweDtcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1NTZmMyAzLTM8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkphcGFuZXNlIn1d

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2008/2009 3번