시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3797 1234 880 30.524%

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입력 1

7 5
100
400
300
100
500
101
400

예제 출력 1

500
W3sicHJvYmxlbV9pZCI6IjYyMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YTlcdWIzYzggXHVhZDAwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNmE5XHViM2M4XHVjNzQ0IFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWQ2NWNcdWM2YTlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWM5ZGNcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNTVlXHVjNzNjXHViODVjIE5cdWM3N2MgXHViM2Q5XHVjNTQ4IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHViM2M4XHVjNzQ0IFx1ZDM5MVx1ZDM5MSBcdWM0ZjBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggTVx1YmM4OFx1YjljYyZuYnNwO1x1ZDFiNVx1YzdhNVx1YzVkMFx1YzExYyBcdWIzYzhcdWM3NDQgXHViZTdjXHVjMTFjIFx1YzRmMFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuJm5ic3A7XHVkNjA0XHVjNmIwXHViMjk0IFx1ZDFiNVx1YzdhNVx1YzVkMFx1YzExYyBLXHVjNmQwXHVjNzQ0IFx1Yzc3OFx1Y2Q5Y1x1ZDU1OFx1YmE3MCwgXHVkMWI1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YmU4MCZuYnNwO1x1YjNjOFx1YzczY1x1Yjg1YyBcdWQ1NThcdWI4ZThcdWI5N2MgXHViY2Y0XHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVhZGY4XHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWNlMCwgXHViYWE4XHVjNzkwXHViNzdjXHVhYzhjIFx1YjQxOFx1YmE3NCBcdWIwYThcdWM3NDAgXHVhZTA4XHVjNTYxXHVjNzQwIFx1ZDFiNVx1YzdhNVx1YzVkMCBcdWM5ZDFcdWM1YjRcdWIxMjNcdWFjZTAgXHViMmU0XHVjMmRjIEtcdWM2ZDBcdWM3NDQgXHVjNzc4XHVjZDljXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5Y2MgXHVkNjA0XHVjNmIwXHViMjk0IE1cdWM3NzRcdWI3N2NcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1ZDY1NVx1ZDc4OCBNXHViYzg4XHVjNzQ0IFx1YjlkZVx1Y2Q5NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViMGE4XHVjNzQwIFx1YWUwOFx1YzU2MVx1Yzc3NCBcdWFkZjhcdWIwYTAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YWUwOFx1YzU2MVx1YmNmNFx1YjJlNCBcdWI5Y2VcdWIzNTRcdWI3N2NcdWIzYzQgXHViMGE4XHVjNzQwIFx1YWUwOFx1YzU2MVx1Yzc0MCBcdWQxYjVcdWM3YTVcdWM1ZDAgXHVjOWQxXHVjNWI0XHViMTIzXHVhY2UwIFx1YjJlNFx1YzJkYyBLXHVjNmQwXHVjNzQ0IFx1Yzc3OFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHViM2M4XHVjNzQ0IFx1YzU0NFx1YjA3Y1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzc4XHVjZDljIFx1YWUwOFx1YzU2MSBLXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWUwOFx1YzU2MSBLXHViOTdjJm5ic3A7XHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4xXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwmbmJzcDsxICZsZTsgTSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPjJcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWM2YjBcdWFjMDAgaVx1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YWUwOFx1YzU2MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgXHVhZTA4XHVjNTYxICZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjA0XHVjNmIwXHVhYzAwIFx1ZDFiNVx1YzdhNVx1YzVkMFx1YzExYyBcdWM3NzhcdWNkOWNcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1Y2Q1Y1x1YzE4YyBcdWFlMDhcdWM1NjEgS1x1Yjk3YyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MjM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9udGhseSBFeHBlbnNlIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBpcyBhbiBhc3RvdW5kaW5nIGFjY291bnRpbmcgd2l6YXJkIGFuZCBoYXMgcmVhbGl6ZWQgaGUgbWlnaHQgcnVuIG91dCBvZiBtb25leSB0byBydW4gdGhlIGZhcm0uIEhlIGhhcyBhbHJlYWR5IGNhbGN1bGF0ZWQgYW5kIHJlY29yZGVkIHRoZSBleGFjdCBhbW91bnQgb2YgbW9uZXkgKDEgJmxlOyBtb25leTxzdWI+aTxcL3N1Yj4gJmxlOyAxMCwwMDApIHRoYXQgaGUgd2lsbCBuZWVkIHRvIHNwZW5kIGVhY2ggZGF5IG92ZXIgdGhlIG5leHQgTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKSBkYXlzLjxcL3A+XHJcblxyXG48cD5GSiB3YW50cyB0byBjcmVhdGUgYSBidWRnZXQgZm9yIGEgc2VxdWVudGlhbCBzZXQgb2YgZXhhY3RseSBNICgxICZsZTsgTSAmbGU7IE4pIGZpc2NhbCBwZXJpb2RzIGNhbGxlZCAmcXVvdDtmYWpvbW9udGhzJnF1b3Q7LiBFYWNoIG9mIHRoZXNlIGZham9tb250aHMgY29udGFpbnMgYSBzZXQgb2YgMSBvciBtb3JlIGNvbnNlY3V0aXZlIGRheXMuIEV2ZXJ5IGRheSBpcyBjb250YWluZWQgaW4gZXhhY3RseSBvbmUgZmFqb21vbnRoLjxcL3A+XHJcblxyXG48cD5GSiYjMzk7cyBnb2FsIGlzIHRvIGFycmFuZ2UgdGhlIGZham9tb250aHMgc28gYXMgdG8gbWluaW1pemUgdGhlIGV4cGVuc2VzIG9mIHRoZSBmYWpvbW9udGggd2l0aCB0aGUgaGlnaGVzdCBzcGVuZGluZyBhbmQgdGh1cyBkZXRlcm1pbmUgaGlzIG1vbnRobHkgc3BlbmRpbmcgbGltaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgZG9sbGFycyBGYXJtZXIgSm9obiBzcGVuZHMgb24gdGhlIGl0aCBkYXk8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgc21hbGxlc3QgcG9zc2libGUgbW9udGhseSBsaW1pdCBGYXJtZXIgSm9obiBjYW4gYWZmb3JkIHRvIGxpdmUgd2l0aC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO March 2007 Contest > Silver 3번