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

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 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(0 ≤ Di ≤ 10,000)가 차례차례 주어진다.

출력

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

예제 입력 1

5 2
5
3
4
2
10

예제 출력 1

9

힌트

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

W3sicHJvYmxlbV9pZCI6IjE3NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWNcdWI4MjRcdWIyZWNcdWI4MjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YzgxYywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViNFx1YzgxYyBcdWM1YjRcdWM4MWMgXHViMmU4XHVjY2I0XHViMmVjXHViOWFjXHVhZTMwXHViOTdjIFx1YjQ1MCBcdWJjODhcdWM3NzRcdWIwOTggXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NTggXHVjNzc0XHViN2VjXHVkNTVjIFx1ZDU1OFx1YjRkYyBcdWQyYjhcdWI4MDhcdWM3NzRcdWIyZGRcdWM3M2NcdWI4NWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWNjYjRcdWI4MjVcdWM3NDAgXHVhYzcwXHVjNzU4IFx1YmMxNVx1YzljMFx1YzEzMSBcdWMyMThcdWM5MDBcdWM3NzQgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNmQ0XHViNGRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM2YjRcdWIzZDlcdWM3YTVcdWM3NDQgXHViM2M0XHViMjk0XHViMzcwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBOXHViZDg0XHVjNWQwIFx1YzY0NFx1YzhmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzJkY1x1YWMwNCBcdWM1NDhcdWJjMzBcdWIyYTVcdWI4MjVcdWFlNGNcdWM5YzAgXHVhYzE2XHVjZDk0XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViNzk4XHVjMTFjIE5cdWJkODRcdWIzZDlcdWM1NDggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjJlY1x1YjliNFx1YzljMCBcdWM1NDRcdWIyZDggXHVjMjc0XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWIzYzQgXHVjNzc4XHVhYzA0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjYzRcdWMxOGQgXHViMmVjXHViOWI0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjIDFcdWJkODRcdWM3NDQgXHViMmVjXHViOWIwXHViMmU0XHViYTc0ICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1YjI5NCAxXHVjNzc0IFx1YzYyY1x1Yjc3Y1x1YWMwNFx1YjJlNC4gXHViYzE4XHViMzAwXHViODVjIDFcdWJkODRcdWM3NDQgXHVjMjcwXHViMmU0XHViYTc0ICZsZHF1bztcdWM5YzBcdWNlNjggXHVjOWMwXHVjMjE4JnJkcXVvO1x1YjI5NCAxXHVjNzc0IFx1YjBiNFx1YjgyNFx1YWMwNFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1Yzc3NCAmbGRxdW87XHVjOWMwXHVjZTY4IFx1YzljMFx1YzIxOCZyZHF1bztcdWFjMDAgTVx1YmNmNFx1YjJlNCBcdWNlZTRcdWM5YzBcdWJhNzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViMmVjXHViOWI0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1YzhmYyBcdWQyYjlcdWM3NzRcdWQ1NThcdWFjOGNcdWIzYzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViOWNjXHVjNTdkIElcdWJkODRcdWM1ZDAgXHViMmVjXHViODM4XHViMmU0XHViYTc0IEQ8c3ViPmk8XC9zdWI+IFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViMmVjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChpXHViZDg0XHVjNzQ0IFx1YjJlY1x1YjgzOFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjIElcdWJkODRcdWM3NzQgXHViNDE4XHViMjk0IFx1YjU0Y1x1YzVkMCBcdWIyZWNcdWI4MzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzg0KSBcdWI2MTBcdWQ1NWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzI2Y1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzQgXHVjOWMwXHVjZTY4XHVjOWMwXHVjMjE4XHVhYzAwIDBcdWM3NzQgXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWMyZGMgXHViMmVjXHViOWI0IFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzY1x1Yjg2MCBcdWM3NzQgXHViMmVjXHViOWFjXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5OFx1YmE3NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHViMmU0XHVjMmRjIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmVjXHViOWFjXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5Y1x1YjJlNFx1Yzc0YyBcdWM5YzBcdWNlNjhcdWM5YzBcdWMyMThcdWFjMDAgMFx1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YjlkMVx1Yzc0MCBcdWM4MTVcdWMyZTBcdWM3M2NcdWI4NWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIyZWNcdWI5YWNcdWFlMzBcdWFjMDAgXHViMDVkXHViMDk4XHViYTc0IFx1YzljMFx1Y2U2OFx1YzljMFx1YzIxOFx1YjI5NCAwXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkNFx1YjRkY1x1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYTQwXHViOWFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiNFx1YjNkOVx1ZDU2MCBcdWMyZGNcdWFjMDQgTigxICZsZTsgTiAmbGU7IDEwMDAwKVx1YWNmYyBNKDEgJmxlOyBNICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGlcdWJkODRcdWM1ZDAgXHViMmVjXHViOWI0XHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWMgRDxzdWI+aTxcL3N1Yj4oMCAmbGU7IEQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAsMDAwKVx1YWMwMCBcdWNjMjhcdWI4NDBcdWNjMjhcdWI4NDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwXHViODVjIFx1YmE0MFx1YjlhYyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xXHViZDg0XHVjNWQwIDVcdWI5Y2NcdWQwN2MgXHViNmYwXHVhY2UwIDJcdWJkODRcdWI1NGMgXHVjMjZjXHVhY2UwIDNcdWJkODRcdWM1ZDAgXHViNmYwXHVjNWI0XHVjMTFjIDRcdWI5N2MgXHViMzU0IFx1YjZmMFx1YWNlMCA0IDVcdWJkODRcdWM3NDAgXHVjMjcwXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTc1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJ1bm5pbmciLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGFyZSB0cnlpbmcgdG8gYmVjb21lIGJldHRlciBhdGhsZXRlcywgc28gQmVzc2llIGlzIHJ1bm5pbmcgb24gYSB0cmFjayBmb3IgZXhhY3RseSBOICgxICZsZTsmbmJzcDtOICZsZTsgMTAsMDAwKSBtaW51dGVzLiBEdXJpbmcgZWFjaCBtaW51dGUsIHNoZSBjYW4gY2hvb3NlIHRvIGVpdGhlciBydW4gb3IgcmVzdCBmb3IgdGhlIHdob2xlIG1pbnV0ZS48XC9wPlxyXG5cclxuPHA+VGhlIHVsdGltYXRlIGRpc3RhbmNlIEJlc3NpZSBydW5zLCB0aG91Z2gsIGRlcGVuZHMgb24gaGVyICYjMzk7ZXhoYXVzdGlvbiBmYWN0b3ImIzM5Oywgd2hpY2ggc3RhcnRzIGF0IDAuIFdoZW4gc2hlIGNob29zZXMgdG8gcnVuIGluIG1pbnV0ZSBpLCBzaGUgd2lsbCBydW4gZXhhY3RseSBhIGRpc3RhbmNlIG9mIEQ8c3ViPmk8XC9zdWI+ICgxICZsZTsgRDxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCkgYW5kIGhlciBleGhhdXN0aW9uIGZhY3RvciB3aWxsIGluY3JlYXNlIGJ5IDEgLS0gYnV0IG11c3QgbmV2ZXIgYmUgYWxsb3dlZCB0byBleGNlZWQgTSAoMSAmbGU7IE0gJmxlOyA1MDApLiAmbmJzcDtJZiBzaGUgY2hvb3NlcyB0byByZXN0LCBoZXIgZXhoYXVzdGlvbiBmYWN0b3Igd2lsbCBkZWNyZWFzZSBieSAxIGZvciBlYWNoIG1pbnV0ZSBzaGUgcmVzdHMuIFNoZSBjYW5ub3QgY29tbWVuY2UgcnVubmluZyBhZ2FpbiB1bnRpbCBoZXIgZXhoYXVzdGlvbiBmYWN0b3IgcmVhY2hlcyAwLiBBdCB0aGF0IHBvaW50LCBzaGUgY2FuIGNob29zZSB0byBydW4gb3IgcmVzdC48XC9wPlxyXG5cclxuPHA+QXQgdGhlIGVuZCBvZiB0aGUgTiBtaW51dGUgd29ya291dCwgQmVzc2llJiMzOTtzIGV4YXVzdGlvbiBmYWN0b3IgbXVzdCBiZSBleGFjdGx5IDAsIG9yIHNoZSB3aWxsIG5vdCBoYXZlIGVub3VnaCBlbmVyZ3kgbGVmdCBmb3IgdGhlIHJlc3Qgb2YgdGhlIGRheS48XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbWF4aW1hbCBkaXN0YW5jZSBCZXNzaWUgY2FuIHJ1bi48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdGhlIHNpbmdsZSBpbnRlZ2VyOiBEPHN1Yj5pPFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBsYXJnZXN0IGRpc3RhbmNlIEJlc3NpZSBjYW4gcnVuIHdoaWxlIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+QmVzc2llIHJ1bnMgZHVyaW5nIHRoZSBmaXJzdCBtaW51dGUgKGRpc3RhbmNlPTUpLCByZXN0cyBkdXJpbmcgdGhlIHNlY29uZCBtaW51dGUsIHJ1bnMgZm9yIHRoZSB0aGlyZCAoZGlzdGFuY2U9NCksIGFuZCByZXN0cyBmb3IgdGhlIGZvdXJ0aCBhbmQgZmlmdGguIE5vdGUgdGhhdCBCZXNzaWUgY2Fubm90IHJ1biBvbiB0aGUgZmlmdGggbWludXRlIGJlY2F1c2Ugc2hlIHdvdWxkIG5vdCBlbmQgd2l0aCBhIHJlc3QgZmFjdG9yIG9mIDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

  • 문제를 번역한 사람: author9