시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 83 30 14 36.842%

문제

파머 존스의 소들은 동전 게임 하는 것을 좋아해서 파머 존스는 소들을 위해 두 명에서 할 수 있는 Xoinc라는 동전 게임을 만들었다.

처음에 N개의 코인이 바닥에 쌓여있다. (꼭대기에서 i번째에 있는 동전의 가치는 C_i이다)

첫 번째 사람은 꼭대기에서 한 개 혹은 두 개의 동전을 가져간다. 만일 첫 번째 사람이 꼭대기에 있는 동전만 가져갔을 경우, 두 번째 사람은 한 개 또는 두 개의 동전만 가져갈 수 있다. 만일 첫 번째 사람이 두 개의 동전을 가져갔을 경우, 두 번째 선수는 한 개부터 네 개의 동전을 가져갈 수 있다. 각각의 턴마다, 동전을 가져가는 사람은 최소 한 개부터 전 사람이 가져간 동전의 두 배까지 가져갈 수 있다. 더 이상 가져갈 동전이 없다면 게임이 끝난다.

이후에, 게임에서 얻은 동전으로 파머 존스에게서 물건을 살 수 있다. 그러므로, 그들은 최대한 많은 돈을 가져가야 한다. 두 번째 사람이 게임에서 돈을 최대로 얻기 위해 최적의 상황으로 돈을 가져간다고 가정한다면, 게임이 끝났을 때 첫 번째 사람이 가져갈 수 있는 돈의 최대값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 동전의 개수 N이 주어진다. (5 <= N <= 2,000)

두 번째 줄부터 N+1 번째 줄까지는 C_i가 주어진다. (1 <= C_i <= 100,000)

출력

첫 번째 줄에 첫 번째 사람이 가져갈 수 있는 돈의 최대값을 출력한다.

예제 입력 1

5
1
3
1
7
2

예제 출력 1

9

힌트

1, 3, 1, 7, 2의 가치가 있는 동전이 있다.

첫 번째 사람은 동전 한 개를 가져간다 (가치 : 1). 상대편은 똑같이 한 개를 가져간다 (가치 : 3). 다시 첫 번째 사람은 두 개의 동전을 가져간다 (가치 : 1,7 -- 합계 : 9). 마지막으로 상대편은 남은 동전을 가져간다 (가치 : 2 -- 합계 : 5).

W3sicHJvYmxlbV9pZCI6IjYwMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWM4MDQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzMGNcdWJhMzggXHVjODc0XHVjMmE0XHVjNzU4IFx1YzE4Y1x1YjRlNFx1Yzc0MCBcdWIzZDlcdWM4MDQgXHVhYzhjXHVjNzg0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTc0XHVjMTFjIFx1ZDMwY1x1YmEzOCBcdWM4NzRcdWMyYTRcdWIyOTQgXHVjMThjXHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NCZuYnNwO1x1YjQ1MCBcdWJhODVcdWM1ZDBcdWMxMWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgWG9pbmNcdWI3N2NcdWIyOTQgXHViM2Q5XHVjODA0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0Y1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1Y2Y1NFx1Yzc3OFx1Yzc3NCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHVjMzEzXHVjNWVjXHVjNzg4XHViMmU0LiAoXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwXHVjMTFjIGlcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgQ19pXHVjNzc0XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWFmMmRcdWIzMDBcdWFlMzBcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YWMxYyBcdWQ2MzlcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LiBcdWI5Y2NcdWM3N2MgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhZjJkXHViMzAwXHVhZTMwXHVjNWQwIFx1Yzc4OFx1YjI5NCZuYnNwO1x1YjNkOVx1YzgwNFx1YjljYyBcdWFjMDBcdWM4MzhcdWFjMTRcdWM3NDQgXHVhY2JkXHVjNmIwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWQ1NWMgXHVhYzFjIFx1YjYxMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjNkOVx1YzgwNFx1YjljYyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNzdjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHVjNzc0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMxNFx1Yzc0NCBcdWFjYmRcdWM2YjAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMTIwXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWFjMWNcdWJkODBcdWQxMzAgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxMzRcdWI5YzhcdWIyZTQsIFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2Q1Y1x1YzE4YyBcdWQ1NWMgXHVhYzFjXHViZDgwXHVkMTMwIFx1YzgwNCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA0IFx1YjNkOVx1YzgwNFx1Yzc1OCBcdWI0NTAgXHViYzMwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWIzZDlcdWM4MDRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNFx1YzVkMCwgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjJm5ic3A7XHVjNWJiXHVjNzQwIFx1YjNkOVx1YzgwNFx1YzczY1x1Yjg1YyBcdWQzMGNcdWJhMzggXHVjODc0XHVjMmE0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWMwYjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViYmMwXHViODVjLCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWIzYzhcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YjNjOFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVjNWJiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWM4MDFcdWM3NTggXHVjMGMxXHVkNjY5XHVjNzNjXHViODVjIFx1YjNjOFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0XHViYTc0LCZuYnNwO1x1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwYWNcdWM3NDQgXHViNTRjJm5ic3A7XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViM2M4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHViM2Q5XHVjODA0XHVjNzU4IFx1YWMxY1x1YzIxOCZuYnNwO05cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoNSAmbHQ7PSBOICZsdDs9IDIsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzEgXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMFx1YjI5NCBDX2lcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBDX2kgJmx0Oz0gMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzYzhcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MSwgMywgMSwgNywgMlx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHVjNzQwIFx1YjNkOVx1YzgwNCBcdWQ1NWMgXHVhYzFjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwNFx1YjJlNCAoXHVhYzAwXHVjZTU4IDogMSkuIFx1YzBjMVx1YjMwMFx1ZDNiOFx1Yzc0MCBcdWI2MTFcdWFjMTlcdWM3NzQgXHVkNTVjIFx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTQgKFx1YWMwMFx1Y2U1OCA6IDMpLiBcdWIyZTRcdWMyZGMgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIzZDlcdWM4MDRcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0IChcdWFjMDBcdWNlNTggOiZuYnNwOzEsNyAtLSBcdWQ1NjlcdWFjYzQgOiA5KS4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YzBjMVx1YjMwMFx1ZDNiOFx1Yzc0MCBcdWIwYThcdWM3NDAgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwNFx1YjJlNCAoXHVhYzAwXHVjZTU4IDombmJzcDsyIC0tIFx1ZDU2OVx1YWNjNCA6IDUpLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjAwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkEgQ29pbiBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBjb3dzIGxpa2UgdG8gcGxheSBjb2luIGdhbWVzIHNvIEZKIGhhcyBpbnZlbnRlZCB3aXRoIGEgbmV3IHR3by1wbGF5ZXIgY29pbiBnYW1lIGNhbGxlZCBYb2luYyBmb3IgdGhlbS48XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5IGEgc3RhY2sgb2YgTiAoNSAmbHQ7PSBOICZsdDs9IDIsMDAwKSBjb2lucyBzaXRzIG9uIHRoZSBncm91bmQ7IGNvaW4gaSBmcm9tIHRoZSB0b3AgaGFzIGludGVnZXIgdmFsdWUgQ19pICgxICZsdDs9IENfaSAmbHQ7PSAxMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IHBsYXllciBzdGFydHMgdGhlIGdhbWUgYnkgdGFraW5nIHRoZSB0b3Agb25lIG9yIHR3byBjb2lucyAoQ18xIGFuZCBtYXliZSBDXzIpIGZyb20gdGhlIHN0YWNrLiBJZiB0aGUgZmlyc3QgcGxheWVyIHRha2VzIGp1c3QgdGhlIHRvcCBjb2luLCB0aGUgc2Vjb25kIHBsYXllciBtYXkgdGFrZSB0aGUgZm9sbG93aW5nIG9uZSBvciB0d28gY29pbnMgaW4gdGhlIG5leHQgdHVybi4gSWYgdGhlIGZpcnN0IHBsYXllciB0YWtlcyB0d28gY29pbnMgdGhlbiB0aGUgc2Vjb25kIHBsYXllciBtYXkgdGFrZSB0aGUgdG9wIG9uZSwgdHdvLCB0aHJlZSBvciBmb3VyIGNvaW5zIGZyb20gdGhlIHN0YWNrLiBJbiBlYWNoIHR1cm4sIHRoZSBjdXJyZW50IHBsYXllciBtdXN0IHRha2UgYXQgbGVhc3Qgb25lIGNvaW4gYW5kIGF0IG1vc3QgdHdvIHRpbWVzIHRoZSBhbW91bnQgb2YgY29pbnMgbGFzdCB0YWtlbiBieSB0aGUgb3Bwb3NpbmcgcGxheWVyLiBUaGUgZ2FtZSBpcyBvdmVyIHdoZW4gdGhlcmUgYXJlIG5vIG1vcmUgY29pbnMgdG8gdGFrZS48XC9wPlxyXG5cclxuPHA+QWZ0ZXJ3YXJkcywgdGhleSBjYW4gdXNlIHRoZSB2YWx1ZSBvZiB0aGUgY29pbnMgdGhleSBoYXZlIHRha2VuIGZyb20gdGhlIHN0YWNrIHRvIGJ1eSB0cmVhdHMgZnJvbSBGSiwgc28gbmF0dXJhbGx5LCB0aGVpciBwdXJwb3NlIGluIHRoZSBnYW1lIGlzIHRvIG1heGltaXplIHRoZSB0b3RhbCB2YWx1ZSBvZiB0aGUgY29pbnMgdGhleSB0YWtlLiBBc3N1bWluZyB0aGUgc2Vjb25kIHBsYXllciBwbGF5cyBvcHRpbWFsbHkgdG8gbWF4aW1pemUgaGlzIG93biB3aW5uaW5ncywgd2hhdCBpcyB0aGUgaGlnaGVzdCB0b3RhbCB2YWx1ZSB0aGF0IHRoZSBmaXJzdCBwbGF5ZXIgY2FuIGhhdmUgd2hlbiB0aGUgZ2FtZSBpcyBvdmVyPzxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyOiBDX2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG1heGltdW0gdmFsdWUgdGhhdCBjYW4gYmUgbWFkZSBieSB0aGUgZmlyc3QgcGxheWVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGVyZSBhcmUgZml2ZSBjb2lucyB3aXRoIHRoZSB2YWx1ZXMgMSwgMywgMSwgNywgYW5kIDIuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBwbGF5ZXIgc3RhcnRzIGJ5IHRha2luZyBhIHNpbmdsZSBjb2luICh2YWx1ZSAxKS4gVGhlIG9wcG9uZW50IHRha2VzIG9uZSBjb2luIGFzIHdlbGwgKHZhbHVlIDMpLiBUaGUgZmlyc3QgcGxheWVyIHRha2VzIHR3byBtb3JlIGNvaW5zICh2YWx1ZXMgMSBhbmQgNyAtLSB0b3RhbCA5KS4gVGhlIHNlY29uZCBwbGF5ZXIgZ2V0cyB0aGUgbGVmdG92ZXIgY29pbiAodmFsdWUgMi0tIHRvdGFsIDUpLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d