시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 78 35 32 52.459%

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 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+XHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwIFx1YzZiNFx1YjNkOVx1ZDU2MCBcdWMyZGNcdWFjMDQoTiZsdDs9MTAwMDApXHVhY2ZjIE0oJmx0Oz01MDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWM3NzRcdWM1YjRcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgSVx1YmQ4NFx1YzVkMCBcdWIyZWNcdWI5YjRcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNjMjhcdWI4NDBcdWNjMjhcdWI4NDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOFx1YzkwNFx1YzVkMCBcdWNkNWNcdWIzMDBcdWI4NWMgXHViYTQwXHViOWFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWJkODRcdWM1ZDAgNVx1YjljY1x1ZDA3YyBcdWI2ZjBcdWFjZTAgMlx1YmQ4NFx1YjU0YyBcdWMyNmNcdWFjZTAgM1x1YmQ4NFx1YzVkMCBcdWI2ZjBcdWM1YjRcdWMxMWMgNFx1Yjk3YyBcdWIzNTQgXHViNmYwXHVhY2UwIDQgNVx1YmQ4NFx1Yzc0MCBcdWMyNzBcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUnVubmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvd3MgYXJlIHRyeWluZyB0byBiZWNvbWUgYmV0dGVyIGF0aGxldGVzLCBzbyBCZXNzaWUgaXMgcnVubmluZyBvbiBhIHRyYWNrIGZvciBleGFjdGx5IE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIG1pbnV0ZXMuIER1cmluZyBlYWNoIG1pbnV0ZSwgc2hlIGNhbiBjaG9vc2UgdG8gZWl0aGVyIHJ1biBvciByZXN0IGZvciB0aGUgd2hvbGUgbWludXRlLjxcL3A+XHJcblxyXG48cD5UaGUgdWx0aW1hdGUgZGlzdGFuY2UgQmVzc2llIHJ1bnMsIHRob3VnaCwgZGVwZW5kcyBvbiBoZXIgJiMzOTtleGhhdXN0aW9uIGZhY3RvciYjMzk7LCB3aGljaCBzdGFydHMgYXQgMC4gV2hlbiBzaGUgY2hvb3NlcyB0byBydW4gaW4gbWludXRlIGksIHNoZSB3aWxsIHJ1biBleGFjdGx5IGEgZGlzdGFuY2Ugb2YgRF9pICgxICZsdDs9IERfaSAmbHQ7PSAxLDAwMCkgYW5kIGhlciBleGhhdXN0aW9uIGZhY3RvciB3aWxsIGluY3JlYXNlIGJ5IDEgLS0gYnV0IG11c3QgbmV2ZXIgYmUgYWxsb3dlZCB0byBleGNlZWQgTSAoMSAmbHQ7PSBNICZsdDs9IDUwMCkuICZuYnNwO0lmIHNoZSBjaG9vc2VzIHRvIHJlc3QsIGhlciBleGhhdXN0aW9uIGZhY3RvciB3aWxsIGRlY3JlYXNlIGJ5IDEgZm9yIGVhY2ggbWludXRlIHNoZSByZXN0cy4gU2hlIGNhbm5vdCBjb21tZW5jZSBydW5uaW5nIGFnYWluIHVudGlsIGhlciBleGhhdXN0aW9uIGZhY3RvciByZWFjaGVzIDAuIEF0IHRoYXQgcG9pbnQsIHNoZSBjYW4gY2hvb3NlIHRvIHJ1biBvciByZXN0LjxcL3A+XHJcblxyXG48cD5BdCB0aGUgZW5kIG9mIHRoZSBOIG1pbnV0ZSB3b3Jrb3V0LCBCZXNzaWUmIzM5O3MgZXhhdXN0aW9uIGZhY3RvciBtdXN0IGJlIGV4YWN0bHkgMCwgb3Igc2hlIHdpbGwgbm90IGhhdmUgZW5vdWdoIGVuZXJneSBsZWZ0IGZvciB0aGUgcmVzdCBvZiB0aGUgZGF5LjxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBtYXhpbWFsIGRpc3RhbmNlIEJlc3NpZSBjYW4gcnVuLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIE08XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIHRoZSBzaW5nbGUgaW50ZWdlcjogRF9pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBsYXJnZXN0IGRpc3RhbmNlIEJlc3NpZSBjYW4gcnVuIHdoaWxlIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5CZXNzaWUgcnVucyBkdXJpbmcgdGhlIGZpcnN0IG1pbnV0ZSAoZGlzdGFuY2U9NSksIHJlc3RzIGR1cmluZyB0aGUgc2Vjb25kIG1pbnV0ZSwgcnVucyBmb3IgdGhlIHRoaXJkIChkaXN0YW5jZT00KSwgYW5kIHJlc3RzIGZvciB0aGUgZm91cnRoIGFuZCBmaWZ0aC4gTm90ZSB0aGF0IEJlc3NpZSBjYW5ub3QgcnVuIG9uIHRoZSBmaWZ0aCBtaW51dGUgYmVjYXVzZSBzaGUgd291bGQgbm90IGVuZCB3aXRoIGEgcmVzdCBmYWN0b3Igb2YgMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=