시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 14 12 42.857%

문제

상근이는 사다리 게임을 하고 있다. 사다리는 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

힌트

W3sicHJvYmxlbV9pZCI6IjU1NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWIyZTRcdWI5YWMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGFjXHViMmU0XHViOWFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWIyZTRcdWI5YWNcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWMxMzhcdWI4NWNcdWM5MDRcdWFjZmMgbVx1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMTM4XHViODVjXHVjOTA0XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzEzOFx1Yjg1Y1x1YzkwNCBpXHVjNzU4IFx1YzU0NFx1Yjc5OFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IHNpXHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTM4XHViODVjXHVjOTA0IGlcdWM3NTggXHVjMGMxXHViMmU4XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFlMzhcdWM3NDQgXHViNTMwXHViNzdjXHVhYzAwXHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVkNTU4XHViMmU4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhZGY4IFx1YjljOVx1YjMwMFx1YWUzMCBpXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWI1NGMgXHVjNWJiXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWMxMzhcdWI4NWNcdWM5MDQgMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgODBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxOFx1YWNlMCwgMlx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgMTAwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMzhcdWI4NWNcdWM5MDQgMVx1YmQ4MFx1ZDEzMCBcdWMxMzhcdWI4NWNcdWM5MDQga1x1YWU0Y1x1YzljMCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjMTM4XHViODVjXHVjOTA0IGtcdWFjMWNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMzhcdWI4NWNcdWM5MDRcdWM3NTggXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YWNjNFx1YWMwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxYyBcdWM5YzBcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwIFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMGFjXHViMmU0XHViOWFjXHViOTdjIFx1ZDBjMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWMwYWNcdWIyZTRcdWI5YWNcdWM3NTggXHViYWE4XHVjNTkxXHVhY2ZjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMzhcdWI4NWNcdWM5MDRcdWM3NTggXHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEzOFx1Yjg1Y1x1YzkwNFx1Yzc1OCBcdWFjMWNcdWMyMTggbigyICZsZTsgbiAmbGU7IDEwMDApLCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhYzFjXHVjMjE4IG0oMSAmbGU7IG0gJmxlOyAxMDAwMDApLCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0IGgoMiAmbGU7IGggJmxlOyAxMDAwKSwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMxMzhcdWI4NWNcdWM5MDRcdWM3NTggXHVjMjE4IGsoMSAmbGU7IGsgJmxlOyBuKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzhcdWI4NWMgXHViOWM5XHViMzAwXHVjNzU4IFx1ZDU1OFx1YjJlOFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4IHM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHM8c3ViPjE8XC9zdWI+ICsgczxzdWI+MjxcL3N1Yj4gKyAuLi4gKyBzPHN1Yj5uPFwvc3ViPiAmbGU7IDIqMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM5XHViMzAwIGlcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBhPHN1Yj5pPFwvc3ViPlx1YzY0MCBiPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBuLTEsIDEgJmxlOyBiPHN1Yj5pPFwvc3ViPiAmbGU7IGgtMSkgXHViOWM5XHViMzAwIGlcdWIyOTQgXHVjMTM4XHViODVjXHVjOTA0IGE8c3ViPmk8XC9zdWI+XHVjNjQwIGE8c3ViPmk8XC9zdWI+KzFcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHVhY2UwLCBcdWMwYzFcdWIyZThcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzBcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIGI8c3ViPmk8XC9zdWI+XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NhZGFyaS5wbmdcIiBzdHlsZT1cIndpZHRoOiAxNzlweDsgaGVpZ2h0OiAyNzFweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1NzIiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTMwNDJcdTMwN2ZcdTMwNjBcdTMwNGZcdTMwNTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZiBKIFx1NTQxYlx1MzA2OFx1NGUwMFx1N2RkMlx1MzA2Ylx1MzA0Mlx1MzA3Zlx1MzA2MFx1MzA0Zlx1MzA1OFx1MzA5Mlx1NGY3Zlx1MzA2M1x1MzA2Nlx1OTA0YVx1MzA5M1x1MzA2N1x1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA0Mlx1MzA3Zlx1MzA2MFx1MzA0Zlx1MzA1OFx1MzA2ZiBuIFx1NjcyY1x1MzA2ZVx1N2UyNlx1NjhkMlx1MzA2OG0gXHU2NzJjXHUzMDZlXHU2YTJhXHU2OGQyXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlXHU3ZTI2XHU2OGQyXHUzMDZiXHUzMDZmXHU1ZGU2XHUzMDRiXHUzMDg5XHU5ODA2XHUzMDZiIDEgXHUzMDRiXHUzMDg5IG4gXHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDRjXHUzMDY0XHUzMDQ0XHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjXHU3ZTI2XHU2OGQyIGkgXHUzMDZlXHU0ZTBiXHU3YWVmXHUzMDZiXHUzMDZmXHU2YjYzXHU2NTc0XHU2NTcwIHM8c3ViPmk8XC9zdWI+IFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NkcjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjY4cHg7IHdpZHRoOjE2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1NTZmMyAzLTEgXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDZlXHU0ZjhiXHVmZjA4biA9IDQsIG0gPSA1LCBzPHN1Yj4xPFwvc3ViPiA9IDIwLCBzPHN1Yj4yPFwvc3ViPiA9IDgwLCBzPHN1Yj4zPFwvc3ViPiA9IDEwMCwgczxzdWI+NDxcL3N1Yj4gPSA1MFx1ZmYwOTxcL3A+XHJcblxyXG48cD5cdTdlMjZcdTY4ZDIgaSBcdTMwNmVcdTRlMDBcdTc1NmFcdTRlMGFcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmJcdTkwNTNcdTMwOTJcdTMwNWZcdTMwNjlcdTMwNjNcdTMwNjZcdTMwNDRcdTMwNGRcdTUyMzBcdTkwNTRcdTMwNTdcdTMwNWZcdTRlMGJcdTdhZWZcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTY1NzRcdTY1NzBcdTMwNGNcdWZmMGNcdTdlMjZcdTY4ZDIgaSBcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjBcdTU4MzRcdTU0MDhcdTMwNmVcdTVmOTdcdTcwYjlcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTRmOGJcdTMwNDhcdTMwNzBcdWZmMGNcdTU2ZjMgMy0xIFx1MzA2N1x1MzA2Zlx1ZmYwY1x1N2UyNlx1NjhkMiAxIFx1MzA5Mlx1OTA3OFx1MzA3Nlx1MzA2OFx1NWY5N1x1NzBiOVx1MzA2ZiA4MCBcdTcwYjlcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTdlMjZcdTY4ZDIgMiBcdTMwOTJcdTkwNzhcdTMwNzZcdTMwNjhcdTVmOTdcdTcwYjlcdTMwNmYgMTAwIFx1NzBiOVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NkcjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjY2cHg7IHdpZHRoOjQwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1NTZmMyAzLTIgXHU5MDUzXHUzMDZlXHUzMDVmXHUzMDY5XHUzMDhhXHU2NWI5XHUzMDZlXHU0ZjhiPFwvcD5cclxuXHJcbjxwPkogXHU1NDFiXHUzMDZmXHU3ZTI2XHU2OGQyIDEgXHUzMDRiXHUzMDg5XHU3ZTI2XHU2OGQyIGsgXHUzMDdlXHUzMDY3XHUzMDZlXHU5MDIzXHU3ZDlhXHUzMDU3XHUzMDVmIGsgXHU2NzJjXHUzMDkyXHU5MDc4XHUzMDc2XHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDVmXHVmZjBlXHUzMDVkXHUzMDhjXHUzMDg5IGsgXHU2NzJjXHUzMDZlXHU3ZTI2XHU2OGQyXHUzMDkyXHU5MDc4XHUzMDkzXHUzMDYwXHUzMDY4XHUzMDRkXHUzMDZlXHU3MGI5XHU2NTcwXHUzMDZlXHU1NDA4XHU4YTA4XHUzMDRjIEogXHU1NDFiXHUzMDZlXHU1Zjk3XHU3MGI5XHUzMDY4XHUzMDZhXHUzMDhiXHVmZjBlXHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHU1MTg1XHUzMDZlXHU2YTJhXHU2OGQyXHUzMDkyXHU0ZTAwXHU2NzJjXHU5MDc4XHUzMDczXHVmZjBjXHUzMDVkXHUzMDZlXHU2YTJhXHU2OGQyXHUzMDkyXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDRiXHUzMDg5XHU1MjRhXHU5NjY0XHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlXHVmZjA4XHU1MjRhXHU5NjY0XHUzMDU3XHUzMDZhXHUzMDRmXHUzMDY2XHUzMDgyXHUzMDg4XHUzMDQ0XHVmZjBlXHVmZjA5XHUzMDgyXHUzMDU3XHVmZjBjXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHU2YTJhXHU2OGQyXHUzMDkyXHU0ZTAwXHU2NzJjXHU1MjRhXHU5NjY0XHUzMDU3XHUzMDVmXHU1ODM0XHU1NDA4XHUzMDZmXHVmZjBjXHU1MjRhXHU5NjY0XHU1ZjhjXHUzMDZlXHUzMDQyXHUzMDdmXHUzMDYwXHUzMDRmXHUzMDU4XHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHVmZjBjXHU3ZTI2XHU2OGQyIDEgXHUzMDRiXHUzMDg5XHU3ZTI2XHU2OGQyIGsgXHUzMDdlXHUzMDY3XHUzMDZlXHU5MDIzXHU3ZDlhXHUzMDU3XHUzMDVmIGsgXHU2NzJjXHUzMDZlXHU3ZTI2XHU2OGQyXHUzMDkyXHU5MDc4XHUzMDkzXHUzMDYwXHUzMDY4XHUzMDRkXHUzMDZlXHU3MGI5XHU2NTcwXHUzMDZlXHU1NDA4XHU4YTA4XHUzMDRjIEogXHU1NDFiXHUzMDZlXHU1Zjk3XHU3MGI5XHUzMDY4XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTI5Ylx1MzA2OFx1MzA1N1x1MzA2Nlx1MzA0Mlx1MzA3Zlx1MzA2MFx1MzA0Zlx1MzA1OFx1MzA2ZVx1NWY2Mlx1MzA2OCBKIFx1NTQxYlx1MzA2ZVx1OTA3OFx1MzA3Nlx1N2UyNlx1NjhkMlx1MzA2ZVx1NjcyY1x1NjU3MCBrIFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY0ogXHU1NDFiXHUzMDZlXHU1Zjk3XHU3MGI5XHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2ZiA0IFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBuLCBtLCBoLCBrIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2N1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZW4gKDIgJmxlOyBuICZsZTsgMTAwMCkgXHUzMDZmXHU3ZTI2XHU2OGQyXHUzMDZlXHU2NzJjXHU2NTcwXHUzMDkyXHVmZjBjbSAoMSAmbGU7IG0gJmxlOyAxMDAwMDApIFx1MzA2Zlx1NmEyYVx1NjhkMlx1MzA2ZVx1NjcyY1x1NjU3MFx1MzA5Mlx1ZmYwY2ggKDIgJmxlOyBoICZsZTsgMTAwMCkgXHUzMDZmXHU3ZTI2XHU2OGQyXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDkyXHVmZjBjayAoMSAmbGU7IGsgJmxlOyBuKSBcdTMwNmYgSiBcdTU0MWJcdTMwNGNcdTkwNzhcdTMwNzZcdTdlMjZcdTY4ZDJcdTMwNmVcdTY3MmNcdTY1NzBcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU3ZDlhXHUzMDRmIG4gXHU4ODRjXHUzMDZiXHUzMDZmXHU3ZTI2XHU2OGQyXHUzMDZlXHU0ZTBiXHU3YWVmXHUzMDZiXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHU3MGI5XHU2NTcwXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlaSsxIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBuKVx1MzA2Ylx1MzA2Zlx1NmI2M1x1NjU3NFx1NjU3MCBzPHN1Yj5pPFwvc3ViPiBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNzPHN1Yj4xPFwvc3ViPiArIHM8c3ViPjI8XC9zdWI+ICsgJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgKyBzPHN1Yj5uPFwvc3ViPiAmbGU7IDIwMDAwMDAwMDAgPSAyICZ0aW1lczsgMTA8c3VwPjk8XC9zdXA+IFx1MzA5Mlx1NmU4MFx1MzA1Zlx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTdkOWFcdTMwNGYgbSBcdTg4NGNcdTMwNmJcdTMwNmZcdTZhMmFcdTY4ZDJcdTMwNmVcdTRmNGRcdTdmNmVcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTZhMmFcdTY4ZDJcdTMwNmJcdTMwNmYgMSBcdTMwNGJcdTMwODkgbSBcdTMwN2VcdTMwNjdcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTMwNjRcdTMwNDRcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVpICsgbiArIDEgXHU4ODRjXHU3NmVlICgxICZsZTsgaSAmbGU7IG0pIFx1MzA2Ylx1MzA2Zlx1ZmYwY1x1NmEyYVx1NjhkMiBpIFx1MzA2ZVx1NGY0ZFx1N2Y2ZVx1MzA5Mlx1ODg2OFx1MzA1OSAyIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4oMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgbiAmbWludXM7IDEsIDEgJmxlOyBiPHN1Yj5pPFwvc3ViPiAmbGU7IGggJm1pbnVzOyAxKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjdcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTZhMmFcdTY4ZDIgaSBcdTMwNGNcdTdlMjZcdTY4ZDIgYTxzdWI+aTxcL3N1Yj4gXHUzMDY4XHU3ZTI2XHU2OGQyIGE8c3ViPmk8XC9zdWI+ICsgMSBcdTMwOTJcdTdkNTBcdTMwNzNcdWZmMGNcdTZhMmFcdTY4ZDIgaSBcdTMwNmVcdTRlMGFcdTdhZWZcdTMwNGJcdTMwODlcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNGMgYmkgXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlXHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjXHUzMDY5XHUzMDZlIDJcdTMwNjRcdTMwNmVcdTZhMmFcdTY4ZDJcdTMwODJcdTdhZWZcdTcwYjlcdTMwOTJcdTUxNzFcdTY3MDlcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTUxZmFcdTUyOWJcdTMwNmZKIFx1NTQxYlx1MzA2ZVx1NWY5N1x1NzBiOVx1MzA2ZVx1NjcwMFx1NWMwZlx1NTAyNFx1MzA2ZVx1MzA3Zlx1MzA5Mlx1NTQyYlx1MzA4MCAxIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NhZGFyaS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzFweDsgd2lkdGg6MTc5cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==

출처

Olympiad > 일본정보올림피아드 > JOI 2009 3번