시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 85 37 34 53.968%

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 N(N<=10000)분에 완주할 수 있는 시간 안배능력까지 갖추게 되었다.

그래서 N분동안 학생들은 달릴지 아님 쉴지 결정하여야 한다. 그러나 학생들도 인간이기 때문에 계속 달릴 수는 없다. “지침 지수”라는 것이 있어서 1분을 달린다면 “지침 지수”는 1이 올라간다. 반대로 1분을 쉰다면 “지침 지수”는 1이 내려간다. 또한 이 “지침 지수”가 M(M<=500)보다 커지면 학생들은 더 이상 달릴 수가 없다.

아주 특이하게도 학생들은 시간에 따라 달릴 수 있는 거리가 다르다. 만약 I분에 달렸다면 D_i 만큼의 거리를 달릴 수 있다. (i분을 달렸다는 것이 아니라 I분이 되는 때에 달렸다는 뜻임) 또한 학생들이 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수가 없다.

물론 이 달리기가 끝나면 학생들은 다시 공부를 해야한다. 그렇기 때문에 달리기가 끝난다음 지침지수가 0이 되지 않는다면 맑은 정신으로 문제를 풀 수가 없기 때문에 달리기가 끝나면 지침지수는 0이 되어야 한다.

월드학생들이 최대한 멀리 갈 수 있는 거리를 구해보자.

입력

첫째 줄에 운동할 시간(N<=10000)과 M(<=500)이 주어진다. 이어서 N개의 줄에 I분에 달릴수 있는 거리가 차례차례 주어진다.

출력

첫째 줄에 최대로 멀리 갈 수 있는 거리를 출력하라.

예제 입력 1

5 2
5
3
4
2
10

예제 출력 1

9

힌트

1분에 5만큼 뛰고 2분때 쉬고 3분에 뛰어서 4를 더 뛰고 4 5분은 쉰다.

W3sicHJvYmxlbV9pZCI6IjE3NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWNcdWI4MjRcdWIyZWNcdWI4MjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YzgxYywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViNFx1YzgxYyBcdWM1YjRcdWM4MWMgXHViMmU4XHVjY2I0XHViMmVjXHViOWFjXHVhZTMwXHViOTdjIFx1YjQ1MCBcdWJjODhcdWM3NzRcdWIwOTggXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NTggXHVjNzc0XHViN2VjXHVkNTVjIFx1ZDU1OFx1YjRkYyBcdWQyYjhcdWI4MDhcdWM3NzRcdWIyZGRcdWM3M2NcdWI4NWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWNjYjRcdWI4MjVcdWM3NDAgXHVhYzcwXHVjNzU4IFx1YmMxNVx1YzljMFx1YzEzMSBcdWMyMThcdWM5MDBcdWM3NzQgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM2YjRcdWIzZDlcdWM3YTVcdWM3NDQgXHViM2M0XHViMjk0XHViMzcwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBOKE4mbHQ7PTEwMDAwKVx1YmQ4NFx1YzVkMCBcdWM2NDRcdWM4ZmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyZGNcdWFjMDQgXHVjNTQ4XHViYzMwXHViMmE1XHViODI1XHVhZTRjXHVjOWMwIFx1YWMxNlx1Y2Q5NFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yjc5OFx1YzExYyBOXHViZDg0XHViM2Q5XHVjNTQ4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWIyZWNcdWI5YjRcdWM5YzAgXHVjNTQ0XHViMmQ4IFx1YzI3NFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVkNTU5XHVjMGRkXHViNGU0XHViM2M0IFx1Yzc3OFx1YWMwNFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhY2M0XHVjMThkIFx1YjJlY1x1YjliNCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LiAmbGRxdW87XHVjOWMwXHVjZTY4IFx1YzljMFx1YzIxOCZyZHF1bztcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExYyAxXHViZDg0XHVjNzQ0IFx1YjJlY1x1YjliMFx1YjJlNFx1YmE3NCAmbGRxdW87XHVjOWMwXHVjZTY4IFx1YzljMFx1YzIxOCZyZHF1bztcdWIyOTQgMVx1Yzc3NCBcdWM2MmNcdWI3N2NcdWFjMDRcdWIyZTQuIFx1YmMxOFx1YjMwMFx1Yjg1YyAxXHViZDg0XHVjNzQ0IFx1YzI3MFx1YjJlNFx1YmE3NCAmbGRxdW87XHVjOWMwXHVjZTY4IFx1YzljMFx1YzIxOCZyZHF1bztcdWIyOTQgMVx1Yzc3NCBcdWIwYjRcdWI4MjRcdWFjMDRcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWM3NzQgJmxkcXVvO1x1YzljMFx1Y2U2OCBcdWM5YzBcdWMyMTgmcmRxdW87XHVhYzAwIE0oTSZsdDs9NTAwKVx1YmNmNFx1YjJlNCBcdWNlZTRcdWM5YzBcdWJhNzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViMmVjXHViOWI0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1YzhmYyBcdWQyYjlcdWM3NzRcdWQ1NThcdWFjOGNcdWIzYzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViOWNjXHVjNTdkIElcdWJkODRcdWM1ZDAgXHViMmVjXHViODM4XHViMmU0XHViYTc0IERfaSBcdWI5Y2NcdWQwN2NcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YjJlY1x1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoaVx1YmQ4NFx1Yzc0NCBcdWIyZWNcdWI4MzhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzU0NFx1YjJjOFx1Yjc3YyBJXHViZDg0XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWI1NGNcdWM1ZDAgXHViMmVjXHViODM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc4NCkgXHViNjEwXHVkNTVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWMyNmNcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YzljMFx1Y2U2OFx1YzljMFx1YzIxOFx1YWMwMCAwXHVjNzc0IFx1YjQxOFx1YWUzMCBcdWM4MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjMmRjIFx1YjJlY1x1YjliNCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiM2NcdWI4NjAgXHVjNzc0IFx1YjJlY1x1YjlhY1x1YWUzMFx1YWMwMCBcdWIwNWRcdWIwOThcdWJhNzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjJlNFx1YzJkYyBcdWFjZjVcdWJkODBcdWI5N2MgXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjJlY1x1YjlhY1x1YWUzMFx1YWMwMCBcdWIwNWRcdWIwOWNcdWIyZTRcdWM3NGMgXHVjOWMwXHVjZTY4XHVjOWMwXHVjMjE4XHVhYzAwIDBcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWI5ZDFcdWM3NDAgXHVjODE1XHVjMmUwXHVjNzNjXHViODVjIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODAgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmVjXHViOWFjXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5OFx1YmE3NCBcdWM5YzBcdWNlNjhcdWM5YzBcdWMyMThcdWIyOTQgMFx1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDRcdWI0ZGNcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmE0MFx1YjlhYyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2YjRcdWIzZDlcdWQ1NjAgXHVjMmRjXHVhYzA0KE4mbHQ7PTEwMDAwKVx1YWNmYyBNKCZsdDs9NTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIElcdWJkODRcdWM1ZDAgXHViMmVjXHViOWI0XHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjYzI4XHViODQwXHVjYzI4XHViODQwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWJhNDBcdWI5YWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+MVx1YmQ4NFx1YzVkMCA1XHViOWNjXHVkMDdjIFx1YjZmMFx1YWNlMCAyXHViZDg0XHViNTRjIFx1YzI2Y1x1YWNlMCAzXHViZDg0XHVjNWQwIFx1YjZmMFx1YzViNFx1YzExYyA0XHViOTdjIFx1YjM1NCBcdWI2ZjBcdWFjZTAgNCA1XHViZDg0XHVjNzQwIFx1YzI3MFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSdW5uaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY293cyBhcmUgdHJ5aW5nIHRvIGJlY29tZSBiZXR0ZXIgYXRobGV0ZXMsIHNvIEJlc3NpZSBpcyBydW5uaW5nIG9uIGEgdHJhY2sgZm9yIGV4YWN0bHkgTiAoMSAmbHQ7PSBOICZsdDs9IDEwLDAwMCkgbWludXRlcy4gRHVyaW5nIGVhY2ggbWludXRlLCBzaGUgY2FuIGNob29zZSB0byBlaXRoZXIgcnVuIG9yIHJlc3QgZm9yIHRoZSB3aG9sZSBtaW51dGUuPFwvcD5cclxuXHJcbjxwPlRoZSB1bHRpbWF0ZSBkaXN0YW5jZSBCZXNzaWUgcnVucywgdGhvdWdoLCBkZXBlbmRzIG9uIGhlciAmIzM5O2V4aGF1c3Rpb24gZmFjdG9yJiMzOTssIHdoaWNoIHN0YXJ0cyBhdCAwLiBXaGVuIHNoZSBjaG9vc2VzIHRvIHJ1biBpbiBtaW51dGUgaSwgc2hlIHdpbGwgcnVuIGV4YWN0bHkgYSBkaXN0YW5jZSBvZiBEX2kgKDEgJmx0Oz0gRF9pICZsdDs9IDEsMDAwKSBhbmQgaGVyIGV4aGF1c3Rpb24gZmFjdG9yIHdpbGwgaW5jcmVhc2UgYnkgMSAtLSBidXQgbXVzdCBuZXZlciBiZSBhbGxvd2VkIHRvIGV4Y2VlZCBNICgxICZsdDs9IE0gJmx0Oz0gNTAwKS4gJm5ic3A7SWYgc2hlIGNob29zZXMgdG8gcmVzdCwgaGVyIGV4aGF1c3Rpb24gZmFjdG9yIHdpbGwgZGVjcmVhc2UgYnkgMSBmb3IgZWFjaCBtaW51dGUgc2hlIHJlc3RzLiBTaGUgY2Fubm90IGNvbW1lbmNlIHJ1bm5pbmcgYWdhaW4gdW50aWwgaGVyIGV4aGF1c3Rpb24gZmFjdG9yIHJlYWNoZXMgMC4gQXQgdGhhdCBwb2ludCwgc2hlIGNhbiBjaG9vc2UgdG8gcnVuIG9yIHJlc3QuPFwvcD5cclxuXHJcbjxwPkF0IHRoZSBlbmQgb2YgdGhlIE4gbWludXRlIHdvcmtvdXQsIEJlc3NpZSYjMzk7cyBleGF1c3Rpb24gZmFjdG9yIG11c3QgYmUgZXhhY3RseSAwLCBvciBzaGUgd2lsbCBub3QgaGF2ZSBlbm91Z2ggZW5lcmd5IGxlZnQgZm9yIHRoZSByZXN0IG9mIHRoZSBkYXkuPFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIG1heGltYWwgZGlzdGFuY2UgQmVzc2llIGNhbiBydW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTTxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdGhlIHNpbmdsZSBpbnRlZ2VyOiBEX2k8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIGxhcmdlc3QgZGlzdGFuY2UgQmVzc2llIGNhbiBydW4gd2hpbGUgc2F0aXNmeWluZyB0aGUgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkJlc3NpZSBydW5zIGR1cmluZyB0aGUgZmlyc3QgbWludXRlIChkaXN0YW5jZT01KSwgcmVzdHMgZHVyaW5nIHRoZSBzZWNvbmQgbWludXRlLCBydW5zIGZvciB0aGUgdGhpcmQgKGRpc3RhbmNlPTQpLCBhbmQgcmVzdHMgZm9yIHRoZSBmb3VydGggYW5kIGZpZnRoLiBOb3RlIHRoYXQgQmVzc2llIGNhbm5vdCBydW4gb24gdGhlIGZpZnRoIG1pbnV0ZSBiZWNhdXNlIHNoZSB3b3VsZCBub3QgZW5kIHdpdGggYSByZXN0IGZhY3RvciBvZiAwLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==