시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 888 303 201 32.315%

문제

현우는 용돈을 효율적으로 활용하기 위해  계획을 짜기로 하였다. 현우는 앞으로 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
W3sicHJvYmxlbV9pZCI6IjYyMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YTlcdWIzYzggXHVhZDAwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNmE5XHViM2M4XHVjNzQ0IFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWQ2NWNcdWM2YTlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0ICZuYnNwO1x1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWM5ZGNcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNTVlXHVjNzNjXHViODVjIE5cdWM3N2MgXHViM2Q5XHVjNTQ4IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHViM2M4XHVjNzQ0IFx1ZDM5MVx1ZDM5MSBcdWM0ZjBcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggTVx1YmM4OFx1YjljYyZuYnNwO1x1ZDFiNVx1YzdhNVx1YzVkMFx1YzExYyBcdWIzYzhcdWM3NDQgXHViZTdjXHVjMTFjIFx1YzRmMFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuJm5ic3A7XHVkNjA0XHVjNmIwXHViMjk0IFx1ZDFiNVx1YzdhNVx1YzVkMFx1YzExYyBLXHVjNmQwXHVjNzQ0IFx1Yzc3OFx1Y2Q5Y1x1ZDU1OFx1YmE3MCwgXHVkMWI1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YmU4MCZuYnNwO1x1YjNjOFx1YzczY1x1Yjg1YyBcdWQ1NThcdWI4ZThcdWI5N2MgXHViY2Y0XHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVhZGY4XHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWNlMCwgXHViYWE4XHVjNzkwXHViNzdjXHVhYzhjIFx1YjQxOFx1YmE3NCBcdWIwYThcdWM3NDAgXHVhZTA4XHVjNTYxXHVjNzQwIFx1ZDFiNVx1YzdhNVx1YzVkMCBcdWM5ZDFcdWM1YjRcdWIxMjNcdWFjZTAgXHViMmU0XHVjMmRjIEtcdWM2ZDBcdWM3NDQgXHVjNzc4XHVjZDljXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5Y2MgXHVkNjA0XHVjNmIwXHViMjk0IE1cdWM3NzRcdWI3N2NcdWIyOTQgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1ZDY1NVx1ZDc4OCBNXHViYzg4XHVjNzQ0IFx1YjlkZVx1Y2Q5NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViMGE4XHVjNzQwIFx1YWUwOFx1YzU2MVx1Yzc3NCBcdWFkZjhcdWIwYTAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YWUwOFx1YzU2MVx1YmNmNFx1YjJlNCBcdWI5Y2VcdWIzNTRcdWI3N2NcdWIzYzQgXHViMGE4XHVjNzQwIFx1YWUwOFx1YzU2MVx1Yzc0MCBcdWQxYjVcdWM3YTVcdWM1ZDAgXHVjOWQxXHVjNWI0XHViMTIzXHVhY2UwIFx1YjJlNFx1YzJkYyBLXHVjNmQwXHVjNzQ0IFx1Yzc3OFx1Y2Q5Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHViM2M4XHVjNzQ0IFx1YzU0NFx1YjA3Y1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzc4XHVjZDljIFx1YWUwOFx1YzU2MSBLXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWUwOFx1YzU2MSBLXHViOTdjJm5ic3A7XHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4xXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwmbmJzcDsxICZsZTsgTSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPjJcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWM2YjBcdWFjMDAgaVx1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YWUwOFx1YzU2MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgXHVhZTA4XHVjNTYxICZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVkMWI1XHVjN2E1XHVjNWQwXHVjMTFjIFx1Yzc3OFx1Y2Q5Y1x1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjZDVjXHVjMThjIFx1YWUwOFx1YzU2MSBLXHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYyMzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb250aGx5IEV4cGVuc2UiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGlzIGFuIGFzdG91bmRpbmcgYWNjb3VudGluZyB3aXphcmQgYW5kIGhhcyByZWFsaXplZCBoZSBtaWdodCBydW4gb3V0IG9mIG1vbmV5IHRvIHJ1biB0aGUgZmFybS4gSGUgaGFzIGFscmVhZHkgY2FsY3VsYXRlZCBhbmQgcmVjb3JkZWQgdGhlIGV4YWN0IGFtb3VudCBvZiBtb25leSAoMSAmbGU7IG1vbmV5aSAmbGU7IDEwLDAwMCkgdGhhdCBoZSB3aWxsIG5lZWQgdG8gc3BlbmQgZWFjaCBkYXkgb3ZlciB0aGUgbmV4dCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIGRheXMuPFwvcD5cclxuXHJcbjxwPkZKIHdhbnRzIHRvIGNyZWF0ZSBhIGJ1ZGdldCBmb3IgYSBzZXF1ZW50aWFsIHNldCBvZiBleGFjdGx5IE0gKDEgJmxlOyBNICZsZTsgTikgZmlzY2FsIHBlcmlvZHMgY2FsbGVkICZxdW90O2Zham9tb250aHMmcXVvdDsuIEVhY2ggb2YgdGhlc2UgZmFqb21vbnRocyBjb250YWlucyBhIHNldCBvZiAxIG9yIG1vcmUgY29uc2VjdXRpdmUgZGF5cy4gRXZlcnkgZGF5IGlzIGNvbnRhaW5lZCBpbiBleGFjdGx5IG9uZSBmYWpvbW9udGguPFwvcD5cclxuXHJcbjxwPkZKJiMzOTtzIGdvYWwgaXMgdG8gYXJyYW5nZSB0aGUgZmFqb21vbnRocyBzbyBhcyB0byBtaW5pbWl6ZSB0aGUgZXhwZW5zZXMgb2YgdGhlIGZham9tb250aCB3aXRoIHRoZSBoaWdoZXN0IHNwZW5kaW5nIGFuZCB0aHVzIGRldGVybWluZSBoaXMgbW9udGhseSBzcGVuZGluZyBsaW1pdC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNJm5ic3A7PFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdGhlIG51bWJlciBvZiBkb2xsYXJzIEZhcm1lciBKb2huIHNwZW5kcyBvbiB0aGUgaXRoIGRheTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgc21hbGxlc3QgcG9zc2libGUgbW9udGhseSBsaW1pdCBGYXJtZXIgSm9obiBjYW4gYWZmb3JkIHRvIGxpdmUgd2l0aC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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