시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 72 30 28 50.909%

문제

동혁이는 낮잠 시간을 N개의 구간으로 나누어서 그 중 B개의 구간동안만 잠을 자려고 한다. B개의 구간이 연속일 필요는 없다. 각 구간동안에 동혁이가 얻을 수 있는 피로 회복량이 정해져 있는데, 동혁이는 이 양을 최대화 하려고 한다. 잠을 설치는 경우가 한 예이다.

예를 들어 구간을 5개로 나누었을 경우, B=3이고 [2 3 4]구간에 잠을 자기로 했다고 치자. 잠을 들기 위해서는 준비 시간이 필요하기 때문에 이 준비 시간 동안에는 피로 회복이 되지 않는다. 각 분할의 첫 구간에서는 피로가 회복되지 않는 것이다. 따라서 [2 3 4] 구간에 잠을 자면 [2]구간에서는 회복을 못하고 [3 4]구간에서만 회복할 수 있다. 이 구간은 N번째 구간과 1번째 구간이 이어져있지 않다고 생각하자.

동혁이가 어떻게 하면 피로회복을 최대로 할 수 있는지 구해보자.

입력

 첫 줄에 N과 B가 주어진다. N은 3이상 3,000이하이고 B는 2이상 N미만이다. 다음으로 N줄에 걸쳐 피로회복량이 주어지는 0이상 200,000 이하의 자연수이다.

출력

 첫 줄에 가능한 최대 피로회복량을 출력한다.

예제 입력 1

5 3
0
3
1
4
2

예제 출력 1

6

힌트

  가령 [1] [4 5]와 같이 선택한다면 0 + 0 + 2 가 된다. (구간을 여러 분할하면 여러 분할의 각 첫 구간은 피로 회복을 할 수 없다) 위의 예에서는 [3 5]구간을 선택하면 0 + 4 + 2 가 되어 최대가 된다.

W3sicHJvYmxlbV9pZCI6IjE5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYWVcdWM3YTAgXHVjMmRjXHVhYzA0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViMGFlXHVjN2EwIFx1YzJkY1x1YWMwNFx1Yzc0NCBOXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWMxMWMgXHVhZGY4IFx1YzkxMSBCXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YjNkOVx1YzU0OFx1YjljYyBcdWM3YTBcdWM3NDQgXHVjNzkwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gQlx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNWYwXHVjMThkXHVjNzdjIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWFjMDRcdWIzZDlcdWM1NDhcdWM1ZDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDUzY1x1Yjg1YyBcdWQ2OGNcdWJjZjVcdWI3YzlcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWM1OTFcdWM3NDQgXHVjZDVjXHViMzAwXHVkNjU0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzdhMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1ZDU1YyBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWFkNmNcdWFjMDRcdWM3NDQgNVx1YWMxY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHVhY2JkXHVjNmIwLCBCPTNcdWM3NzRcdWFjZTAgWzIgMyA0XVx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWM3YTBcdWM3NDQgXHVjNzkwXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNFx1YWNlMCBcdWNlNThcdWM3OTAuIFx1YzdhMFx1Yzc0NCBcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3NzQgXHVjOTAwXHViZTQ0IFx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDhcdWM1ZDBcdWIyOTQgXHVkNTNjXHViODVjIFx1ZDY4Y1x1YmNmNVx1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDEgXHViZDg0XHVkNTYwXHVjNzU4IFx1Y2NhYiBcdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNTNjXHViODVjXHVhYzAwIFx1ZDY4Y1x1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgWzIgMyA0XSBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVjN2EwXHVjNzQ0IFx1Yzc5MFx1YmE3NCBbMl1cdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNjhjXHViY2Y1XHVjNzQ0IFx1YmFiYlx1ZDU1OFx1YWNlMCBbMyA0XVx1YWQ2Y1x1YWMwNFx1YzVkMFx1YzExY1x1YjljYyBcdWQ2OGNcdWJjZjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWQ2Y1x1YWMwNFx1Yzc0MCBOXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YWMwNFx1YWNmYyAxXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM3NzRcdWM1YjRcdWM4MzhcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU1OFx1YmE3NCBcdWQ1M2NcdWI4NWNcdWQ2OGNcdWJjZjVcdWM3NDQgXHVjZDVjXHViMzAwXHViODVjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdCZuYnNwO1x1Y2NhYiBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCAzXHVjNzc0XHVjMGMxIDMsMDAwXHVjNzc0XHVkNTU4XHVjNzc0XHVhY2UwIEJcdWIyOTQgMlx1Yzc3NFx1YzBjMSBOXHViYmY4XHViOWNjXHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM3M2NcdWI4NWMgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVkNTNjXHViODVjXHVkNjhjXHViY2Y1XHViN2M5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCAwXHVjNzc0XHVjMGMxIDIwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHQmbmJzcDtcdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMDAgXHVkNTNjXHViODVjXHVkNjhjXHViY2Y1XHViN2M5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0Jm5ic3A7IFx1YWMwMFx1YjgzOSBbMV0gWzQgNV1cdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNFx1YmE3NCAwICsgMCArIDIgXHVhYzAwIFx1YjQxY1x1YjJlNC4gKFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViZDg0XHVkNTYwXHVkNTU4XHViYTc0IFx1YzVlY1x1YjdlYyBcdWJkODRcdWQ1NjBcdWM3NTggXHVhYzAxIFx1Y2NhYiBcdWFkNmNcdWFjMDRcdWM3NDAgXHVkNTNjXHViODVjIFx1ZDY4Y1x1YmNmNVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNCkgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExY1x1YjI5NCBbMyA1XVx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgMCArIDQgKyAyIFx1YWMwMCBcdWI0MThcdWM1YjQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOYXB0aW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Hb25lcmlsIGlzIGEgdmVyeSBzbGVlcC1kZXByaXZlZCBjb3cuIEhlciBkYXkgaXMgcGFydGl0aW9uZWQgaW50byBOICgzICZsdDs9IE4gJmx0Oz0gMyw4MzApIGVxdWFsIHRpbWUgcGVyaW9kcyBidXQgc2hlIGNhbiBzcGVuZCBvbmx5IEIgKDIgJmx0Oz0gQiAmbHQ7IE4pIG5vdCBuZWNlc3NhcmlseSBjb250aWd1b3VzIHBlcmlvZHMgaW4gYmVkLiBEdWUgdG8gaGVyIGJvdmluZSBob3Jtb25lIGxldmVscywgZWFjaCBwZXJpb2QgaGFzIGl0cyBvd24gdXRpbGl0eSBVX2kgKDAgJmx0Oz0gVV9pICZsdDs9IDIwMCwwMDApLCB3aGljaCBpcyB0aGUgYW1vdW50IG9mIHJlc3QgZGVyaXZlZCBmcm9tIHNsZWVwaW5nIGR1cmluZyB0aGF0IHBlcmlvZC4gVGhlc2UgdXRpbGl0eSB2YWx1ZXMgYXJlIGZpeGVkIGFuZCBhcmUgaW5kZXBlbmRlbnQgb2Ygd2hhdCBHb25lcmlsIGNob29zZXMgdG8gZG8sIGluY2x1ZGluZyB3aGVuIHNoZSBkZWNpZGVzIHRvIGJlIGluIGJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2l0aCB0aGUgaGVscCBvZiBoZXIgYWxhcm0gY2xvY2ssIHNoZSBjYW4gY2hvb3NlIGV4YWN0bHkgd2hpY2ggcGVyaW9kcyB0byBzcGVuZCBpbiBiZWQgYW5kIHdoaWNoIHBlcmlvZHMgdG8gc3BlbmQgZG9pbmcgbW9yZSBjcml0aWNhbCBpdGVtcyBzdWNoIGFzIHdyaXRpbmcgcGFwZXJzIG9yIHdhdGNoaW5nIGJhc2ViYWxsLiBIb3dldmVyLCBzaGUgY2FuIG9ubHkgZ2V0IGluIG9yIG91dCBvZiBiZWQgb24gdGhlIGJvdW5kYXJpZXMgb2YgYSBwZXJpb2QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNoZSB3YW50cyB0byBjaG9vc2UgaGVyIHNsZWVwaW5nIHBlcmlvZHMgdG8gbWF4aW1pemUgdGhlIHN1bSBvZiB0aGUgdXRpbGl0aWVzIG92ZXIgdGhlIHBlcmlvZHMgZHVyaW5nIHdoaWNoIHNoZSBpcyBpbiBiZWQuIFVuZm9ydHVuYXRlbHksIGV2ZXJ5IHRpbWUgc2hlIGNsaW1icyBpbiBiZWQsIHNoZSBoYXMgdG8gc3BlbmQgdGhlIGZpcnN0IHBlcmlvZCBmYWxsaW5nIGFzbGVlcCBhbmQgZ2V0cyBubyBzbGVlcCB1dGlsaXR5IGZyb20gdGhhdCBwZXJpb2QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwZXJpb2RzIHdyYXAgYXJvdW5kIGluIGEgY2lyY2xlOyBpZiBHb25lcmlsIHNwZW5kcyBib3RoIHBlcmlvZHMgTiBhbmQgMSBpbiBiZWQsIHRoZW4gc2hlIGRvZXMgZ2V0IHNsZWVwIHV0aWxpdHkgb3V0IG9mIHBlcmlvZCAxLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGF0IGlzIHRoZSBtYXhpbXVtIHRvdGFsIHNsZWVwIHV0aWxpdHkgR29uZXJpbCBjYW4gYWNoaWV2ZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBCJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyLCBVX2ksIGJldHdlZW4gMCBhbmQgMjAwLDAwMCBpbmNsdXNpdmU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZGF5IGlzIGRpdmlkZWQgaW50byA1IHBlcmlvZHMsIHdpdGggdXRpbGl0aWVzIDIsIDAsIDMsIDEsIDQgaW4gdGhhdCBvcmRlci4gR29uZXJpbCBtdXN0IHBpY2sgMyBwZXJpb2RzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SU5QVVQgREVUQUlMUzombmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGRheSBpcyBkaXZpZGVkIGludG8gNSBwZXJpb2RzLCB3aXRoIHV0aWxpdGllcyAyLCAwLCAzLCAxLCA0IGluIHRoYXQgb3JkZXIuIEdvbmVyaWwgbXVzdCBwaWNrIDMgcGVyaW9kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T1VUUFVUIERFVEFJTFM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkdvbmVyaWwgY2FuIGdldCB0b3RhbCB1dGlsaXR5IDYgYnkgYmVpbmcgaW4gYmVkIGR1cmluZyBwZXJpb2RzIDQsIDUsIGFuZCAxLCB3aXRoIHV0aWxpdGllcyAwIFtnZXR0aW5nIHRvIHNsZWVwXSwgNCwgYW5kIDIgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d