시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 205 71 61 37.423%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

5 2
5
3
4
2
10

예제 출력 1

9

힌트

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

W3sicHJvYmxlbV9pZCI6IjE3NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWNcdWI4MjRcdWIyZWNcdWI4MjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YzgxYywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViNFx1YzgxYyBcdWM1YjRcdWM4MWMgXHViMmU4XHVjY2I0XHViMmVjXHViOWFjXHVhZTMwXHViOTdjIFx1YjQ1MCBcdWJjODhcdWM3NzRcdWIwOTggXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NTggXHVjNzc0XHViN2VjXHVkNTVjIFx1ZDU1OFx1YjRkYyBcdWQyYjhcdWI4MDhcdWM3NzRcdWIyZGRcdWM3M2NcdWI4NWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWNjYjRcdWI4MjVcdWM3NDAgXHVhYzcwXHVjNzU4IFx1YmMxNVx1YzljMFx1YzEzMSBcdWMyMThcdWM5MDBcdWM3NzQgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM2YjRcdWIzZDlcdWM3YTVcdWM3NDQgXHViM2M0XHViMjk0XHViMzcwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBOXHViZDg0XHVjNWQwIFx1YzY0NFx1YzhmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNCBcdWM1NDhcdWJjMzBcdWIyYTVcdWI4MjVcdWFlNGNcdWM5YzAgXHVhYzE2XHVjZDk0XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViNzk4XHVjMTFjIE5cdWJkODRcdWIzZDlcdWM1NDggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjJlY1x1YjliNFx1YzljMCBcdWM1NDRcdWIyZDggXHVjMjc0XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWIzYzQgXHVjNzc4XHVhYzA0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjYzRcdWMxOGQgXHViMmVjXHViOWI0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjIDFcdWJkODRcdWM3NDQgXHViMmVjXHViOWIwXHViMmU0XHViYTc0ICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1YjI5NCAxXHVjNzc0IFx1YzYyY1x1Yjc3Y1x1YWMwNFx1YjJlNC4gXHViYzE4XHViMzAwXHViODVjIDFcdWJkODRcdWM3NDQgXHVjMjcwXHViMmU0XHViYTc0ICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1YjI5NCAxXHVjNzc0IFx1YjBiNFx1YjgyNFx1YWMwNFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCAmbGRxdW87XHVjOWMwXHVjZTY4IFx1YzljMFx1YzIxOCZyZHF1bztcdWFjMDAgTVx1YmNmNFx1YjJlNCBcdWNlZTRcdWM5YzBcdWJhNzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViMmVjXHViOWI0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1YzhmYyBcdWQyYjlcdWM3NzRcdWQ1NThcdWFjOGNcdWIzYzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViOWNjXHVjNTdkIElcdWJkODRcdWM1ZDAgXHViMmVjXHViODM4XHViMmU0XHViYTc0IEQ8c3ViPmk8XC9zdWI+IFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChpXHViZDg0XHVjNzQ0IFx1YjJlY1x1YjgzOFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjIElcdWJkODRcdWM3NzQgXHViNDE4XHViMjk0IFx1YjU0Y1x1YzVkMCBcdWIyZWNcdWI4MzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzg0KSBcdWI2MTBcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzI2Y1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzQgXHVjOWMwXHVjZTY4XHVjOWMwXHVjMjE4XHVhYzAwIDBcdWM3NzQgXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWMyZGMgXHViMmVjXHViOWI0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzY1x1Yjg2MCBcdWM3NzQgXHViMmVjXHViOWFjXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5OFx1YmE3NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHViMmU0XHVjMmRjIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmVjXHViOWFjXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5Y1x1YjJlNFx1Yzc0YyBcdWM5YzBcdWNlNjhcdWM5YzBcdWMyMThcdWFjMDAgMFx1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YjlkMVx1Yzc0MCBcdWM4MTVcdWMyZTBcdWM3M2NcdWI4NWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIyZWNcdWI5YWNcdWFlMzBcdWFjMDAgXHViMDVkXHViMDk4XHViYTc0IFx1YzljMFx1Y2U2OFx1YzljMFx1YzIxOFx1YjI5NCAwXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkNFx1YjRkY1x1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYTQwXHViOWFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiNFx1YjNkOVx1ZDU2MCBcdWMyZGNcdWFjMDQgTigxICZsZTsgTiAmbGU7IDEwMDAwKVx1YWNmYyBNKDEgJmxlOyBNICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGlcdWJkODRcdWM1ZDAgXHViMmVjXHViOWI0XHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWMgRDxzdWI+aTxcL3N1Yj4oMSAmbGU7IEQ8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDApXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1Y2MyOFx1Yjg0MCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWIzMDBcdWI4NWMgXHViYTQwXHViOWFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWJkODRcdWM1ZDAgNVx1YjljY1x1ZDA3YyBcdWI2ZjBcdWFjZTAgMlx1YmQ4NFx1YjU0YyBcdWMyNmNcdWFjZTAgM1x1YmQ4NFx1YzVkMCBcdWI2ZjBcdWM1YjRcdWMxMWMgNFx1Yjk3YyBcdWIzNTQgXHViNmYwXHVhY2UwIDQgNVx1YmQ4NFx1Yzc0MCBcdWMyNzBcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUnVubmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvd3MgYXJlIHRyeWluZyB0byBiZWNvbWUgYmV0dGVyIGF0aGxldGVzLCBzbyBCZXNzaWUgaXMgcnVubmluZyBvbiBhIHRyYWNrIGZvciBleGFjdGx5IE4gKDEgJmxlOyZuYnNwO04gJmxlOyAxMCwwMDApIG1pbnV0ZXMuIER1cmluZyBlYWNoIG1pbnV0ZSwgc2hlIGNhbiBjaG9vc2UgdG8gZWl0aGVyIHJ1biBvciByZXN0IGZvciB0aGUgd2hvbGUgbWludXRlLjxcL3A+XHJcblxyXG48cD5UaGUgdWx0aW1hdGUgZGlzdGFuY2UgQmVzc2llIHJ1bnMsIHRob3VnaCwgZGVwZW5kcyBvbiBoZXIgJiMzOTtleGhhdXN0aW9uIGZhY3RvciYjMzk7LCB3aGljaCBzdGFydHMgYXQgMC4gV2hlbiBzaGUgY2hvb3NlcyB0byBydW4gaW4gbWludXRlIGksIHNoZSB3aWxsIHJ1biBleGFjdGx5IGEgZGlzdGFuY2Ugb2YgRDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBEPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKSBhbmQgaGVyIGV4aGF1c3Rpb24gZmFjdG9yIHdpbGwgaW5jcmVhc2UgYnkgMSAtLSBidXQgbXVzdCBuZXZlciBiZSBhbGxvd2VkIHRvIGV4Y2VlZCBNICgxICZsZTsgTSAmbGU7IDUwMCkuICZuYnNwO0lmIHNoZSBjaG9vc2VzIHRvIHJlc3QsIGhlciBleGhhdXN0aW9uIGZhY3RvciB3aWxsIGRlY3JlYXNlIGJ5IDEgZm9yIGVhY2ggbWludXRlIHNoZSByZXN0cy4gU2hlIGNhbm5vdCBjb21tZW5jZSBydW5uaW5nIGFnYWluIHVudGlsIGhlciBleGhhdXN0aW9uIGZhY3RvciByZWFjaGVzIDAuIEF0IHRoYXQgcG9pbnQsIHNoZSBjYW4gY2hvb3NlIHRvIHJ1biBvciByZXN0LjxcL3A+XHJcblxyXG48cD5BdCB0aGUgZW5kIG9mIHRoZSBOIG1pbnV0ZSB3b3Jrb3V0LCBCZXNzaWUmIzM5O3MgZXhhdXN0aW9uIGZhY3RvciBtdXN0IGJlIGV4YWN0bHkgMCwgb3Igc2hlIHdpbGwgbm90IGhhdmUgZW5vdWdoIGVuZXJneSBsZWZ0IGZvciB0aGUgcmVzdCBvZiB0aGUgZGF5LjxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBtYXhpbWFsIGRpc3RhbmNlIEJlc3NpZSBjYW4gcnVuLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIE08XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyB0aGUgc2luZ2xlIGludGVnZXI6IEQ8c3ViPmk8XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIGxhcmdlc3QgZGlzdGFuY2UgQmVzc2llIGNhbiBydW4gd2hpbGUgc2F0aXNmeWluZyB0aGUgY29uZGl0aW9ucy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5CZXNzaWUgcnVucyBkdXJpbmcgdGhlIGZpcnN0IG1pbnV0ZSAoZGlzdGFuY2U9NSksIHJlc3RzIGR1cmluZyB0aGUgc2Vjb25kIG1pbnV0ZSwgcnVucyBmb3IgdGhlIHRoaXJkIChkaXN0YW5jZT00KSwgYW5kIHJlc3RzIGZvciB0aGUgZm91cnRoIGFuZCBmaWZ0aC4gTm90ZSB0aGF0IEJlc3NpZSBjYW5ub3QgcnVuIG9uIHRoZSBmaWZ0aCBtaW51dGUgYmVjYXVzZSBzaGUgd291bGQgbm90IGVuZCB3aXRoIGEgcmVzdCBmYWN0b3Igb2YgMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO January 2008 Contest > Silver 2번

  • 문제를 번역한 사람: author9
  • 문제의 오타를 찾은 사람: mulijoa