시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB268947645.509%

문제

동혁이는 낮잠 시간을 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 가 되어 최대가 된다.

W3sicHJvYmxlbV9pZCI6IjE5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYWVcdWM3YTAgXHVjMmRjXHVhYzA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViMGFlXHVjN2EwIFx1YzJkY1x1YWMwNFx1Yzc0NCBOXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWMxMWMgXHVhZGY4IFx1YzkxMSBCXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YjNkOVx1YzU0OFx1YjljYyBcdWM3YTBcdWM3NDQgXHVjNzkwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gQlx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNWYwXHVjMThkXHVjNzdjIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWFjMDRcdWIzZDlcdWM1NDhcdWM1ZDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDUzY1x1Yjg1YyBcdWQ2OGNcdWJjZjVcdWI3YzlcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWM1OTFcdWM3NDQgXHVjZDVjXHViMzAwXHVkNjU0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzdhMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1ZDU1YyBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVhZDZjXHVhYzA0XHVjNzQ0IDVcdWFjMWNcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YWNiZFx1YzZiMCwgQj0zXHVjNzc0XHVhY2UwIFsyIDMgNF1cdWFkNmNcdWFjMDRcdWM1ZDAgXHVjN2EwXHVjNzQ0IFx1Yzc5MFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTRcdWFjZTAgXHVjZTU4XHVjNzkwLiBcdWM3YTBcdWM3NDQgXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM5MDBcdWJlNDQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzc0IFx1YzkwMFx1YmU0NCBcdWMyZGNcdWFjMDQgXHViM2Q5XHVjNTQ4XHVjNWQwXHViMjk0IFx1ZDUzY1x1Yjg1YyBcdWQ2OGNcdWJjZjVcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1YmQ4NFx1ZDU2MFx1Yzc1OCBcdWNjYWIgXHVhZDZjXHVhYzA0XHVjNWQwXHVjMTFjXHViMjk0IFx1ZDUzY1x1Yjg1Y1x1YWMwMCBcdWQ2OGNcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFsyIDMgNF0gXHVhZDZjXHVhYzA0XHVjNWQwIFx1YzdhMFx1Yzc0NCBcdWM3OTBcdWJhNzQgWzJdXHVhZDZjXHVhYzA0XHVjNWQwXHVjMTFjXHViMjk0IFx1ZDY4Y1x1YmNmNVx1Yzc0NCBcdWJhYmJcdWQ1NThcdWFjZTAgWzMgNF1cdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWNcdWI5Y2MgXHVkNjhjXHViY2Y1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFkNmNcdWFjMDRcdWM3NDAgTlx1YmM4OFx1YzlmOCBcdWFkNmNcdWFjMDRcdWFjZmMgMVx1YmM4OFx1YzlmOCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNzc0XHVjNWI0XHVjODM4XHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTU4XHViYTc0IFx1ZDUzY1x1Yjg1Y1x1ZDY4Y1x1YmNmNVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE5cdWFjZmMgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMyBcdWM3NzRcdWMwYzEgMywwMDAgXHVjNzc0XHVkNTU4LCBCXHViMjk0IDIgXHVjNzc0XHVjMGMxIE4gXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM3M2NcdWI4NWMgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVkNTNjXHViODVjXHVkNjhjXHViY2Y1XHViN2M5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVjNzc0IFx1YWMxMlx1Yzc0MCAwIFx1Yzc3NFx1YzBjMSAyMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Jm5ic3A7XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1ZDUzY1x1Yjg1Y1x1ZDY4Y1x1YmNmNVx1YjdjOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMFx1YjgzOSBbMV0gWzQgNV1cdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNFx1YmE3NCAwICsgMCArIDIgXHVhYzAwIFx1YjQxY1x1YjJlNC4gKFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViZDg0XHVkNTYwXHVkNTU4XHViYTc0IFx1YzVlY1x1YjdlYyBcdWJkODRcdWQ1NjBcdWM3NTggXHVhYzAxIFx1Y2NhYiBcdWFkNmNcdWFjMDRcdWM3NDAgXHVkNTNjXHViODVjIFx1ZDY4Y1x1YmNmNVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNCkgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExY1x1YjI5NCBbMyA1XVx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgMCArIDQgKyAyIFx1YWMwMCBcdWI0MThcdWM1YjQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE5ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOYXB0aW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Hb25lcmlsIGlzIGEgdmVyeSBzbGVlcC1kZXByaXZlZCBjb3cuIEhlciBkYXkgaXMgcGFydGl0aW9uZWQgaW50byBOICgzICZsdDs9IE4gJmx0Oz0gMyw4MzApIGVxdWFsIHRpbWUgcGVyaW9kcyBidXQgc2hlIGNhbiBzcGVuZCBvbmx5IEIgKDIgJmx0Oz0gQiAmbHQ7IE4pIG5vdCBuZWNlc3NhcmlseSBjb250aWd1b3VzIHBlcmlvZHMgaW4gYmVkLiBEdWUgdG8gaGVyIGJvdmluZSBob3Jtb25lIGxldmVscywgZWFjaCBwZXJpb2QgaGFzIGl0cyBvd24gdXRpbGl0eSBVX2kgKDAgJmx0Oz0gVV9pICZsdDs9IDIwMCwwMDApLCB3aGljaCBpcyB0aGUgYW1vdW50IG9mIHJlc3QgZGVyaXZlZCBmcm9tIHNsZWVwaW5nIGR1cmluZyB0aGF0IHBlcmlvZC4gVGhlc2UgdXRpbGl0eSB2YWx1ZXMgYXJlIGZpeGVkIGFuZCBhcmUgaW5kZXBlbmRlbnQgb2Ygd2hhdCBHb25lcmlsIGNob29zZXMgdG8gZG8sIGluY2x1ZGluZyB3aGVuIHNoZSBkZWNpZGVzIHRvIGJlIGluIGJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2l0aCB0aGUgaGVscCBvZiBoZXIgYWxhcm0gY2xvY2ssIHNoZSBjYW4gY2hvb3NlIGV4YWN0bHkgd2hpY2ggcGVyaW9kcyB0byBzcGVuZCBpbiBiZWQgYW5kIHdoaWNoIHBlcmlvZHMgdG8gc3BlbmQgZG9pbmcgbW9yZSBjcml0aWNhbCBpdGVtcyBzdWNoIGFzIHdyaXRpbmcgcGFwZXJzIG9yIHdhdGNoaW5nIGJhc2ViYWxsLiBIb3dldmVyLCBzaGUgY2FuIG9ubHkgZ2V0IGluIG9yIG91dCBvZiBiZWQgb24gdGhlIGJvdW5kYXJpZXMgb2YgYSBwZXJpb2QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNoZSB3YW50cyB0byBjaG9vc2UgaGVyIHNsZWVwaW5nIHBlcmlvZHMgdG8gbWF4aW1pemUgdGhlIHN1bSBvZiB0aGUgdXRpbGl0aWVzIG92ZXIgdGhlIHBlcmlvZHMgZHVyaW5nIHdoaWNoIHNoZSBpcyBpbiBiZWQuIFVuZm9ydHVuYXRlbHksIGV2ZXJ5IHRpbWUgc2hlIGNsaW1icyBpbiBiZWQsIHNoZSBoYXMgdG8gc3BlbmQgdGhlIGZpcnN0IHBlcmlvZCBmYWxsaW5nIGFzbGVlcCBhbmQgZ2V0cyBubyBzbGVlcCB1dGlsaXR5IGZyb20gdGhhdCBwZXJpb2QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwZXJpb2RzIHdyYXAgYXJvdW5kIGluIGEgY2lyY2xlOyBpZiBHb25lcmlsIHNwZW5kcyBib3RoIHBlcmlvZHMgTiBhbmQgMSBpbiBiZWQsIHRoZW4gc2hlIGRvZXMgZ2V0IHNsZWVwIHV0aWxpdHkgb3V0IG9mIHBlcmlvZCAxLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGF0IGlzIHRoZSBtYXhpbXVtIHRvdGFsIHNsZWVwIHV0aWxpdHkgR29uZXJpbCBjYW4gYWNoaWV2ZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBCJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyLCBVX2ksIGJldHdlZW4gMCBhbmQgMjAwLDAwMCBpbmNsdXNpdmU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZGF5IGlzIGRpdmlkZWQgaW50byA1IHBlcmlvZHMsIHdpdGggdXRpbGl0aWVzIDIsIDAsIDMsIDEsIDQgaW4gdGhhdCBvcmRlci4gR29uZXJpbCBtdXN0IHBpY2sgMyBwZXJpb2RzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SU5QVVQgREVUQUlMUzombmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGRheSBpcyBkaXZpZGVkIGludG8gNSBwZXJpb2RzLCB3aXRoIHV0aWxpdGllcyAyLCAwLCAzLCAxLCA0IGluIHRoYXQgb3JkZXIuIEdvbmVyaWwgbXVzdCBwaWNrIDMgcGVyaW9kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T1VUUFVUIERFVEFJTFM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkdvbmVyaWwgY2FuIGdldCB0b3RhbCB1dGlsaXR5IDYgYnkgYmVpbmcgaW4gYmVkIGR1cmluZyBwZXJpb2RzIDQsIDUsIGFuZCAxLCB3aXRoIHV0aWxpdGllcyAwIFtnZXR0aW5nIHRvIHNsZWVwXSwgNCwgYW5kIDIgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==