시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 97 12 9 21.429%

문제

요즘 이상한 뉴스가 너무 많아서 그런지, 재현이의 성격은 점점 반사회적이고 폭력적으로 변했다. 얼마 전, 재현 이는 결국 학교의 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+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IDNEIFx1ZDUwNFx1YjliMFx1ZDEzMFx1Yjg1YyBrXHVhYzFjXHVjNzU4IFx1Y2QxZFx1YzU0Y1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWFjZTAsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViNDUwXHViMzU0XHVjOWMwXHViOTdjIFx1Y2FkM1x1YzU0NFx1YjBiNFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Y2QxZFx1Yzc0NCBrXHViYzg4IFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWFjMDAgXHVhZDc0XHVjNzQ0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NFx1YWMwMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwXHViMzU0XHVjOWMwXHVhZDc0XHVjNzU4IFx1YzIxOCBuLCBcdWNkMWRcdWM3NTggXHVjZDVjXHViMzAwIFx1YzBhY1x1YzZhOSBcdWFjMDBcdWIyYTUgXHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoNSAmbGU7IG4gJmxlOyAyMDAwLCAxICZsZTsgayAmbGU7IG4pPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjY8XC9zdXA+KSBpXHViYzg4XHVjOWY4IFx1YWQ3NFx1YzVkMCBhPHN1Yj5pPFwvc3ViPlx1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWFjMDAgXHVjMGIwXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkXHVjNzQ0IGtcdWJjODggXHVjNzc0XHVkNTU4XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1ZDBjOFx1Y2Q5Y1x1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjQ1MFx1YjM1NFx1YzljMCBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjZDA4XHVhZTMwIFx1YjQ1MFx1YjM1NFx1YzljMCBcdWFkNzRcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFs2LCAxLCA1LCAzLCA0XSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YmM4OFx1YzlmOFx1Yjg1YywgXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IDFcdWJjODhcdWM5ZjggXHVhZDc0XHVjNWQwIFx1Y2QxZFx1Yzc0NCBcdWMzZjRcdWMxMWMsIDZcdWI5YzhcdWI5YWNcdWM3NTggXHViNDUwXHViMzU0XHVjOWMwXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1YzJkY1x1ZDBhOFx1YjJlNC4gXHViNDUwXHViMzU0XHVjOWMwIFx1YWQ3NFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWIyOTQgWzAsIDAsIDYsIDcsIDBdXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgNFx1YmM4OFx1YzlmOCBcdWFkNzRcdWM1ZDAgXHVjZDFkXHVjNzQ0IFx1YzNmNFx1YzExYywgN1x1YjljOFx1YjlhY1x1Yzc1OCBcdWI0NTBcdWIzNTRcdWM5YzBcdWI5N2MgXHVkMGM4XHVjZDljXHVjMmRjXHVkMGE4XHViMmU0LiBcdWNkMWQgMTNcdWI5YzhcdWI5YWNcdWFjMDAgXHVkMGM4XHVjZDljXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzk4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJhYmJpdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVhc2FyIGhhcyBkZWNpZGVkIHRvIGdyb3cgbGV0dHVjZSBpbiBoaXMgZ2FyZGVuLiBBcyB5b3UgY2FuIGltYWdpbmUsIEJ5dGVhbiByYWJiaXRzIHNpbXBseSBsb3ZlIGxldHR1Y2UuIFNvLCBub3Qgc3VycHJpc2luZ2x5LCB0aGV5IGluc3RhbnRseSBhcnJpdmVkIGluIEJ5dGVhc2FyJnJzcXVvO3MgZ2FyZGVuLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZ2FyZGVuIHRoZXJlIGFyZSBuIGJlZHMgb2YgbGV0dHVjZSBudW1iZXJlZCAxIHRocm91Z2ggbi4gRXZlcnkgdHdvIHN1YnNlcXVlbnQgYmVkcyBhcmUgYWRqYWNlbnQsIHRoYXQgaXMsIGZvciBlYWNoIGkgPSAxLCAyLCAuLi4sIG4gJm1pbnVzOyAxIHRoZSBiZWRzIG51bWJlciBpIGFuZCBpICsgMSBhcmUgYWRqYWNlbnQgYW5kLCBtb3Jlb3ZlciwgdGhlIGJlZCBudW1iZXIgbiBpcyBhZGphY2VudCB0byB0aGUgYmVkIG51bWJlciAxLiBSaWdodCBub3cgdGhlcmUgYXJlIGFpIHJhYmJpdHMgc3RheWluZyBhdCB0aGUgYmVkIG51bWJlciBpIGFuZCBlYXRpbmcgYXdheSBCeXRlYXNhciZyc3F1bztzIGxldHR1Y2UuPFwvcD5cclxuXHJcbjxwPkJ5dGVhc2FyIHdhbnRzIHRvIGNoYXNlIG91dCBvZiB0aGUgZ2FyZGVuIGFzIG1hbnkgcmFiYml0cyBhcyBwb3NzaWJsZS4gRm9yIHRoaXMgaGUgaXMgZ29pbmcgdG8gdXNlIGhpcyBnb29kIG9sZCBndW4uIFRoZSBndW4gaGFzIGsgYnVsbGV0cyBpbnNpZGUuIFJhYmJpdHMgYXJlIGV4dHJlbWVseSB0aW1pZCwgc28gd2hlbmV2ZXIgQnl0ZWFzYXIgc2hvb3RzIHRvd2FyZHMgdGhlIGJlZCBudW1iZXIgaSwgYWxsIHRoZSByYWJiaXRzIGZyb20gdGhhdCBiZWQgbGVhdmUgQnl0ZWFzYXImcnNxdW87cyBnYXJkZW4gZm9yIGdvb2QuIFdoYXQgaXMgbW9yZSwgdGhlIHJhYmJpdHMgZnJvbSBib3RoIGFkamFjZW50IGJlZHMgYXJlIHNvIGZyaWdodGVuZWQgdGhhdCB0aGV5IGFsbCBtb3ZlIHRvIHRoZSBhZGphY2VudCBiZWQgKG9idmlvdXNseSwgd2UgbWVhbiB0aGUgYWRqYWNlbnQgYmVkIGRpZmZlcmVudCBmcm9tIHRoZSBvbmUgdG93YXJkcyB3aGljaCB3YXMgdGhlIHNob3QpLjxcL3A+XHJcblxyXG48cD5IZWxwIEJ5dGVhc2FyIHRvIGZpbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJhYmJpdHMgdGhhdCBoZSBjYW4gY2hhc2Ugb3V0IG9mIGhpcyBnYXJkZW4gd2l0aCBhdCBtb3N0IGsgc2hvdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgayAoNSAmbGU7IG4gJmxlOyAyMDAwLCAxICZsZTsgayAmbGU7IG4pOiB0aGUgbnVtYmVyIG9mIGJlZHMgb2YgbGV0dHVjZSBpbiB0aGUgZ2FyZGVuIGFuZCB0aGUgbnVtYmVyIG9mIGJ1bGxldHMgQnl0ZWFzYXIgaGFzIGluIGhpcyBndW4uIFRoZSBzZWNvbmQgbGluZSBob2xkcyBuIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiAoMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKTogdGhlIG51bWJlciBvZiByYWJiaXRzIHN0YXlpbmcgYXQgdGhlIHN1YnNlcXVlbnQgYmVkcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBvbmUgaW50ZWdlcjogdGhlIG1heGltdW0gbnVtYmVyIG9mIHJhYmJpdHMgdGhhdCBjYW4gYmUgY2hhc2VkIG91dCBvZiBCeXRlYXNhciZyc3F1bztzIGdhcmRlbiB1c2luZyBhdCBtb3N0IGsgc2hvdHMuPFwvcD5cclxuIiwiaGludCI6IjxwPkV4cGxhbmF0aW9uIG9mIHRoZSBleGFtcGxlOiBGaXJzdCwgQnl0ZWFzYXIgY2hhc2VzIG91dCB0aGUgNiByYWJiaXRzIGZyb20gdGhlIGJlZCBudW1iZXIgMSAoYXMgYSByZXN1bHQsIHRoZSByYWJiaXRzIGZyb20gdGhlIGJlZCBudW1iZXIgNSBtb3ZlIHRvIHRoZSBiZWQgbnVtYmVyIDQsIHdoZXJlYXMgdGhlIHJhYmJpdHMgZnJvbSB0aGUgYmVkIG51bWJlciAyIG1vdmUgdG8gdGhlIGJlZCBudW1iZXIgMykuIE5leHQsIEJ5dGVhc2FyIGNoYXNlcyBvdXQgdGhlIDcgcmFiYml0cyBmcm9tIHRoZSBiZWQgbnVtYmVyIDQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=