시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB170382121.649%

문제

요즘 이상한 뉴스가 너무 많아서 그런지, 재현이의 성격은 점점 반사회적이고 폭력적으로 변했다. 얼마 전, 재현 이는 결국 학교의 3D 프린터를 사용해서 모형 권총을 프린트하고, 혼자 이상한 게임을 하기 시작했다.

재현이는 많은 두더지굴이 있는 잔디밭에서 게임을 시작했다. 잔디밭에는 n개의 두더지굴이 있으며, 두더지굴은 1번부터 n번까지 순서대로 번호가 부여되어 있다. 원형으로 늘어져 있으니, 1번 굴과 2번 굴, 2번 굴과 3번 굴, ..., n번 굴과 1번 굴은 인접해 있다.

현재 각각의 굴에는 ai 마리의 두더지가 있고, 재현이는 모형 권총으로 이들을 쫓아낼 계획이다. 재현이가 모형 권총을 쏴서 i번 굴에 있는 두더지에게 겁을 주면, 그 굴에 있는 두더지들이 겁을 먹고 도망가게 된다. (모형이라 죽지는 않는다.) 뿐만 아니라, 그 굴과 인접한 양 옆 두개의 굴에 있는 두더지들도 겁을 먹어서, 인접한 굴로 이동하게 된다. 당연히, 인접한 굴이라 하면 i번 굴은 아니다.

예를 들어, 10번 굴에 겁을 줬다면, 10번 굴에 있는 두더지는 모두 굴을 탈출하고, 9번 굴에 있는 두더지는 8번 굴로 도망가고, 11번 굴에 있는 두더지는 12번 굴로 도망간다.

재현이는 3D 프린터로 k개의 총알을 만들었고, 최대한 많은 두더지를 쫓아내고 싶다. 총을 k번 이하로 사용했을 때, 최대 몇 마리의 두더지가 굴을 탈출하는가?

입력

첫 번째 줄에 두더지굴의 수 n, 총의 최대 사용 가능 수 k가 주어진다. (5 ≤ n ≤ 2000, 1 ≤ k ≤ n)

이후 n개의 정수 a1, a2, ..., an가 주어진다. (0 ≤ ai ≤ 106) i번째 굴에 ai마리의 두더지가 산다는 것을 의미한다.

출력

총을 k번 이하로 사용했을 때, 탈출시킬 수 있는 두더지 수의 최댓값을 출력한다.

예제 입력 1

5 2
6 1 5 3 4

예제 출력 1

13

힌트

초기 두더지 굴의 상태는 [6, 1, 5, 3, 4] 이다.

첫 번째로, 재현이는 1번째 굴에 총을 쏴서, 6마리의 두더지를 탈출시킨다. 두더지 굴의 상태는 [0, 0, 6, 7, 0]이 된다.

이제, 재현이는 4번째 굴에 총을 쏴서, 7마리의 두더지를 탈출시킨다. 총 13마리가 탈출한다.

W3sicHJvYmxlbV9pZCI6Ijc5ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTBcdWIzNTRcdWM5YzAgXHVjN2ExXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2OTRcdWM5OTggXHVjNzc0XHVjMGMxXHVkNTVjIFx1YjI3NFx1YzJhNFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNTQ0XHVjMTFjIFx1YWRmOFx1YjdmMFx1YzljMCwgXHVjN2FjXHVkNjA0XHVjNzc0XHVjNzU4IFx1YzEzMVx1YWNhOVx1Yzc0MCBcdWM4MTBcdWM4MTAgXHViYzE4XHVjMGFjXHVkNjhjXHVjODAxXHVjNzc0XHVhY2UwIFx1ZDNlZFx1YjgyNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ1ODhcdWIyZTQuIFx1YzViY1x1YjljOCBcdWM4MDQsIFx1YzdhY1x1ZDYwNCBcdWM3NzRcdWIyOTQgXHVhY2IwXHVhZDZkIFx1ZDU1OVx1YWQ1MFx1Yzc1OCAzRCBcdWQ1MDRcdWI5YjBcdWQxMzBcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjIFx1YmFhOFx1ZDYxNSBcdWFkOGNcdWNkMWRcdWM3NDQgXHVkNTA0XHViOWIwXHVkMmI4XHVkNTU4XHVhY2UwLCBcdWQ2M2NcdWM3OTAgXHVjNzc0XHVjMGMxXHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViOWNlXHVjNzQwIFx1YjQ1MFx1YjM1NFx1YzljMFx1YWQ3NFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjNzk0XHViNTE0XHViYzJkXHVjNWQwXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1Yzc5NFx1YjUxNFx1YmMyZFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YjQ1MFx1YjM1NFx1YzljMFx1YWQ3NFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjQ1MFx1YjM1NFx1YzljMFx1YWQ3NFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkODBcdWM1ZWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMjk4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YjJjOCwgMVx1YmM4OCBcdWFkNzRcdWFjZmMgMlx1YmM4OCBcdWFkNzQsIDJcdWJjODggXHVhZDc0XHVhY2ZjIDNcdWJjODggXHVhZDc0LCAuLi4sIG5cdWJjODggXHVhZDc0XHVhY2ZjIDFcdWJjODggXHVhZDc0XHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZDc0XHVjNWQwXHViMjk0IGE8c3ViPmk8XC9zdWI+IFx1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViYWE4XHVkNjE1IFx1YWQ4Y1x1Y2QxZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI0ZTRcdWM3NDQgXHVjYWQzXHVjNTQ0XHViMGJjIFx1YWNjNFx1ZDY4ZFx1Yzc3NFx1YjJlNC4gXHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwIFx1YmFhOFx1ZDYxNSBcdWFkOGNcdWNkMWRcdWM3NDQgXHVjM2Y0XHVjMTFjIGlcdWJjODggXHVhZDc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0NTBcdWIzNTRcdWM5YzBcdWM1ZDBcdWFjOGMgXHVhYzgxXHVjNzQ0IFx1YzhmY1x1YmE3NCwgXHVhZGY4IFx1YWQ3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwXHViMzU0XHVjOWMwXHViNGU0XHVjNzc0IFx1YWM4MVx1Yzc0NCBcdWJhMzlcdWFjZTAgXHViM2M0XHViOWRkXHVhYzAwXHVhYzhjIFx1YjQxY1x1YjJlNC4gKFx1YmFhOFx1ZDYxNVx1Yzc3NFx1Yjc3YyBcdWM4ZmRcdWM5YzBcdWIyOTQgXHVjNTRhXHViMjk0XHViMmU0LikgXHViZmQwXHViOWNjIFx1YzU0NFx1YjJjOFx1Yjc3YywgXHVhZGY4IFx1YWQ3NFx1YWNmYyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjNTkxIFx1YzYwNiBcdWI0NTBcdWFjMWNcdWM3NTggXHVhZDc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0NTBcdWIzNTRcdWM5YzBcdWI0ZTRcdWIzYzQgXHVhYzgxXHVjNzQ0IFx1YmEzOVx1YzViNFx1YzExYywgXHVjNzc4XHVjODExXHVkNTVjIFx1YWQ3NFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWIyZjlcdWM1ZjBcdWQ3ODgsIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFkNzRcdWM3NzRcdWI3N2MgXHVkNTU4XHViYTc0IGlcdWJjODggXHVhZDc0XHVjNzQwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMTBcdWJjODggXHVhZDc0XHVjNWQwIFx1YWM4MVx1Yzc0NCBcdWM5MmNcdWIyZTRcdWJhNzQsIDEwXHViYzg4IFx1YWQ3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwXHViMzU0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFkNzRcdWM3NDQgXHVkMGM4XHVjZDljXHVkNTU4XHVhY2UwLCA5XHViYzg4IFx1YWQ3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwXHViMzU0XHVjOWMwXHViMjk0IDhcdWJjODggXHVhZDc0XHViODVjIFx1YjNjNFx1YjlkZFx1YWMwMFx1YWNlMCwgMTFcdWJjODggXHVhZDc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0NTBcdWIzNTRcdWM5YzBcdWIyOTQgMTJcdWJjODggXHVhZDc0XHViODVjIFx1YjNjNFx1YjlkZFx1YWMwNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IDNEIFx1ZDUwNFx1YjliMFx1ZDEzMFx1Yjg1YyBrXHVhYzFjXHVjNzU4IFx1Y2QxZFx1YzU0Y1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWFjZTAsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViNDUwXHViMzU0XHVjOWMwXHViOTdjIFx1Y2FkM1x1YzU0NFx1YjBiNFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Y2QxZFx1Yzc0NCBrXHViYzg4IFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWFjMDAgXHVhZDc0XHVjNzQ0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NFx1YWMwMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MFx1YjM1NFx1YzljMFx1YWQ3NFx1Yzc1OCBcdWMyMTggbiwgXHVjZDFkXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWMwYWNcdWM2YTkgXHVhYzAwXHViMmE1IFx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDUgJmxlOyBuICZsZTsgMjAwMCwgMSAmbGU7IGsgJmxlOyBuKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgblx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD42PFwvc3VwPikgaVx1YmM4OFx1YzlmOCBcdWFkNzRcdWM1ZDAgYTxzdWI+aTxcL3N1Yj5cdWI5YzhcdWI5YWNcdWM3NTggXHViNDUwXHViMzU0XHVjOWMwXHVhYzAwIFx1YzBiMFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZFx1Yzc0NCBrXHViYzg4IFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQwYzhcdWNkOWNcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI0NTBcdWIzNTRcdWM5YzAgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2QwOFx1YWUzMCBcdWI0NTBcdWIzNTRcdWM5YzAgXHVhZDc0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBbNiwgMSwgNSwgMywgNF0gXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4XHViODVjLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgMVx1YmM4OFx1YzlmOCBcdWFkNzRcdWM1ZDAgXHVjZDFkXHVjNzQ0IFx1YzNmNFx1YzExYywgNlx1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWI5N2MgXHVkMGM4XHVjZDljXHVjMmRjXHVkMGE4XHViMmU0LiBcdWI0NTBcdWIzNTRcdWM5YzAgXHVhZDc0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBbMCwgMCwgNiwgNywgMF1cdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMsIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCA0XHViYzg4XHVjOWY4IFx1YWQ3NFx1YzVkMCBcdWNkMWRcdWM3NDQgXHVjM2Y0XHVjMTFjLCA3XHViOWM4XHViOWFjXHVjNzU4IFx1YjQ1MFx1YjM1NFx1YzljMFx1Yjk3YyBcdWQwYzhcdWNkOWNcdWMyZGNcdWQwYThcdWIyZTQuIFx1Y2QxZCAxM1x1YjljOFx1YjlhY1x1YWMwMCBcdWQwYzhcdWNkOWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3OTg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmFiYml0cyIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZWFzYXIgaGFzIGRlY2lkZWQgdG8gZ3JvdyBsZXR0dWNlIGluIGhpcyBnYXJkZW4uIEFzIHlvdSBjYW4gaW1hZ2luZSwgQnl0ZWFuIHJhYmJpdHMgc2ltcGx5IGxvdmUgbGV0dHVjZS4gU28sIG5vdCBzdXJwcmlzaW5nbHksIHRoZXkgaW5zdGFudGx5IGFycml2ZWQgaW4gQnl0ZWFzYXImcnNxdW87cyBnYXJkZW4uPFwvcD5cclxuXHJcbjxwPkluIHRoZSBnYXJkZW4gdGhlcmUgYXJlIG4gYmVkcyBvZiBsZXR0dWNlIG51bWJlcmVkIDEgdGhyb3VnaCBuLiBFdmVyeSB0d28gc3Vic2VxdWVudCBiZWRzIGFyZSBhZGphY2VudCwgdGhhdCBpcywgZm9yIGVhY2ggaSA9IDEsIDIsIC4uLiwgbiAmbWludXM7IDEgdGhlIGJlZHMgbnVtYmVyIGkgYW5kIGkgKyAxIGFyZSBhZGphY2VudCBhbmQsIG1vcmVvdmVyLCB0aGUgYmVkIG51bWJlciBuIGlzIGFkamFjZW50IHRvIHRoZSBiZWQgbnVtYmVyIDEuIFJpZ2h0IG5vdyB0aGVyZSBhcmUgYWkgcmFiYml0cyBzdGF5aW5nIGF0IHRoZSBiZWQgbnVtYmVyIGkgYW5kIGVhdGluZyBhd2F5IEJ5dGVhc2FyJnJzcXVvO3MgbGV0dHVjZS48XC9wPlxyXG5cclxuPHA+Qnl0ZWFzYXIgd2FudHMgdG8gY2hhc2Ugb3V0IG9mIHRoZSBnYXJkZW4gYXMgbWFueSByYWJiaXRzIGFzIHBvc3NpYmxlLiBGb3IgdGhpcyBoZSBpcyBnb2luZyB0byB1c2UgaGlzIGdvb2Qgb2xkIGd1bi4gVGhlIGd1biBoYXMgayBidWxsZXRzIGluc2lkZS4gUmFiYml0cyBhcmUgZXh0cmVtZWx5IHRpbWlkLCBzbyB3aGVuZXZlciBCeXRlYXNhciBzaG9vdHMgdG93YXJkcyB0aGUgYmVkIG51bWJlciBpLCBhbGwgdGhlIHJhYmJpdHMgZnJvbSB0aGF0IGJlZCBsZWF2ZSBCeXRlYXNhciZyc3F1bztzIGdhcmRlbiBmb3IgZ29vZC4gV2hhdCBpcyBtb3JlLCB0aGUgcmFiYml0cyBmcm9tIGJvdGggYWRqYWNlbnQgYmVkcyBhcmUgc28gZnJpZ2h0ZW5lZCB0aGF0IHRoZXkgYWxsIG1vdmUgdG8gdGhlIGFkamFjZW50IGJlZCAob2J2aW91c2x5LCB3ZSBtZWFuIHRoZSBhZGphY2VudCBiZWQgZGlmZmVyZW50IGZyb20gdGhlIG9uZSB0b3dhcmRzIHdoaWNoIHdhcyB0aGUgc2hvdCkuPFwvcD5cclxuXHJcbjxwPkhlbHAgQnl0ZWFzYXIgdG8gZmluZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcmFiYml0cyB0aGF0IGhlIGNhbiBjaGFzZSBvdXQgb2YgaGlzIGdhcmRlbiB3aXRoIGF0IG1vc3QgayBzaG90cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBrICg1ICZsZTsgbiAmbGU7IDIwMDAsIDEgJmxlOyBrICZsZTsgbik6IHRoZSBudW1iZXIgb2YgYmVkcyBvZiBsZXR0dWNlIGluIHRoZSBnYXJkZW4gYW5kIHRoZSBudW1iZXIgb2YgYnVsbGV0cyBCeXRlYXNhciBoYXMgaW4gaGlzIGd1bi4gVGhlIHNlY29uZCBsaW5lIGhvbGRzIG4gaW50ZWdlcnMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+ICgwICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApOiB0aGUgbnVtYmVyIG9mIHJhYmJpdHMgc3RheWluZyBhdCB0aGUgc3Vic2VxdWVudCBiZWRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IG9uZSBpbnRlZ2VyOiB0aGUgbWF4aW11bSBudW1iZXIgb2YgcmFiYml0cyB0aGF0IGNhbiBiZSBjaGFzZWQgb3V0IG9mIEJ5dGVhc2FyJnJzcXVvO3MgZ2FyZGVuIHVzaW5nIGF0IG1vc3QgayBzaG90cy48XC9wPlxyXG4iLCJoaW50IjoiPHA+RXhwbGFuYXRpb24gb2YgdGhlIGV4YW1wbGU6IEZpcnN0LCBCeXRlYXNhciBjaGFzZXMgb3V0IHRoZSA2IHJhYmJpdHMgZnJvbSB0aGUgYmVkIG51bWJlciAxIChhcyBhIHJlc3VsdCwgdGhlIHJhYmJpdHMgZnJvbSB0aGUgYmVkIG51bWJlciA1IG1vdmUgdG8gdGhlIGJlZCBudW1iZXIgNCwgd2hlcmVhcyB0aGUgcmFiYml0cyBmcm9tIHRoZSBiZWQgbnVtYmVyIDIgbW92ZSB0byB0aGUgYmVkIG51bWJlciAzKS4gTmV4dCwgQnl0ZWFzYXIgY2hhc2VzIG91dCB0aGUgNyByYWJiaXRzIGZyb20gdGhlIGJlZCBudW1iZXIgNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=