시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 87 33 26 36.111%

문제

GSHS 앞에 있는 모 편의점에서 허니버터칩을 무료로 나눠주는 행사를 진행하고 있다! 재현이는 이 기회를 놓칠 수 없어서 무단외출을 감수하고 편의점으로 달려갔다.

편의점에는 N봉지의 허니버터칩이 좌에서 우로 나열되어 있으며, 이 중 i번째 봉지는 Ai개의 과자를 가지고 있다. 추가적으로 M개의 봉지가 더 제공되며, 이 중 i번째 봉지는 Bi개의 과자를 가지고 있다. (봉지가 다 비슷해보이지만 실제 안에 들어 있는 과자의 개수는 천차만별이다)

재현이는 먼저 좌에서 우로 나열되어 있는 N봉지의 허니버터칩 사이에 M개의 봉지를 아무 곳에나 (시작점, 끝점, 봉지 사이) 끼워 넣을 수 있다. 이렇게 되면 N+M 개의 봉지가 좌에서 우로 나열되며 초기의 N 봉지는 상대적 순서를 유지하는 형태가 될 것이다.

재현이는 이렇게 만들어 놓은 리스트를 좌에서 우로 순서대로 걸어가면서 뽑아간다. 재현이는 리스트에 있는 과자를 고를 수도 있고, 안 고를 수도 있지만, 재현이의 걸음이 빠른 편이기 때문에 만약에 과자 한봉지를 가져갔다면 그 다음 과자는 절대 가져갈 수 없다. 다른 말로 하면, 리스트에서 연속된 과자를 고를 수 없다.

재현이가 허니버터칩을 가장 많이 가져갈 수 있도록, 재현이를 도와주자!

입력

첫번째 줄에는 N이 주어진다. 이후 N개의 줄에 Ai가 주어진다. (1 ≤ N ≤ 3,000, 1 ≤ Ai ≤ 100,000)

N+2번째 줄에는 M이 주어진다. 이후 M개의 줄에 Bi가 주어진다. (0 ≤ M ≤ 100, 1 ≤ Bi ≤ 100,000)

출력

재현이가 최대로 가져갈 수 있는 허니버터칩의 개수를 출력하라.

예제 입력 1

5
10
12
6
14
7
3
1
8
2

예제 출력 1

44

힌트

10, 1, 12, 2, 8, 6, 14, 7의 순서가 최적이다.

W3sicHJvYmxlbV9pZCI6IjEwNzc3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNWM4XHViMmM4XHViYzg0XHVkMTMwXHVjZTY5IiwiZGVzY3JpcHRpb24iOiI8cD5HU0hTIFx1YzU1ZVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4IFx1ZDNiOFx1Yzc1OFx1YzgxMFx1YzVkMFx1YzExYyBcdWQ1YzhcdWIyYzhcdWJjODRcdWQxMzBcdWNlNjlcdWM3NDQgXHViYjM0XHViOGNjXHViODVjIFx1YjA5OFx1YjIyMFx1YzhmY1x1YjI5NCBcdWQ1ODlcdWMwYWNcdWI5N2MgXHVjOWM0XHVkNTg5XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNCEgXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFlMzBcdWQ2OGNcdWI5N2MgXHViMTkzXHVjZTYwIFx1YzIxOCBcdWM1YzZcdWM1YjRcdWMxMWMgXHViYjM0XHViMmU4XHVjNjc4XHVjZDljXHVjNzQ0IFx1YWMxMFx1YzIxOFx1ZDU1OFx1YWNlMCBcdWQzYjhcdWM3NThcdWM4MTBcdWM3M2NcdWI4NWMgXHViMmVjXHViODI0XHVhYzE0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYjhcdWM3NThcdWM4MTBcdWM1ZDBcdWIyOTQgTlx1YmQwOVx1YzljMFx1Yzc1OCBcdWQ1YzhcdWIyYzhcdWJjODRcdWQxMzBcdWNlNjlcdWM3NzQgXHVjODhjXHVjNWQwXHVjMTFjIFx1YzZiMFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzQgXHVjOTExIGlcdWJjODhcdWM5ZjggXHViZDA5XHVjOWMwXHViMjk0IEE8c3ViPmk8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWNkOTRcdWFjMDBcdWM4MDFcdWM3M2NcdWI4NWMgTVx1YWMxY1x1Yzc1OCBcdWJkMDlcdWM5YzBcdWFjMDAgXHViMzU0IFx1YzgxY1x1YWNmNVx1YjQxOFx1YmE3MCwgXHVjNzc0IFx1YzkxMSBpXHViYzg4XHVjOWY4IFx1YmQwOVx1YzljMFx1YjI5NCBCPHN1Yj5pPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWFjZmNcdWM3OTBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gKFx1YmQwOVx1YzljMFx1YWMwMCBcdWIyZTQgXHViZTQ0XHVjMmI3XHVkNTc0XHViY2Y0XHVjNzc0XHVjOWMwXHViOWNjIFx1YzJlNFx1YzgxYyBcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjZmNcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2M5Y1x1Y2MyOFx1YjljY1x1YmNjNFx1Yzc3NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1YmEzY1x1YzgwMCBcdWM4OGNcdWM1ZDBcdWMxMWMgXHVjNmIwXHViODVjIFx1YjA5OFx1YzVmNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgTlx1YmQwOVx1YzljMFx1Yzc1OCBcdWQ1YzhcdWIyYzhcdWJjODRcdWQxMzBcdWNlNjkgXHVjMGFjXHVjNzc0XHVjNWQwIE1cdWFjMWNcdWM3NTggXHViZDA5XHVjOWMwXHViOTdjIFx1YzU0NFx1YmIzNCBcdWFjZjNcdWM1ZDBcdWIwOTggKFx1YzJkY1x1Yzc5MVx1YzgxMCwgXHViMDVkXHVjODEwLCBcdWJkMDlcdWM5YzAgXHVjMGFjXHVjNzc0KSBcdWIwN2NcdWM2Y2MgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWI0MThcdWJhNzQgTitNIFx1YWMxY1x1Yzc1OCBcdWJkMDlcdWM5YzBcdWFjMDAgXHVjODhjXHVjNWQwXHVjMTFjIFx1YzZiMFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MThcdWJhNzAgXHVjZDA4XHVhZTMwXHVjNzU4IE4gXHViZDA5XHVjOWMwXHViMjk0IFx1YzBjMVx1YjMwMFx1YzgwMSBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNCBcdWIxOTNcdWM3NDAgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1Yzg4Y1x1YzVkMFx1YzExYyBcdWM2YjBcdWI4NWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWM3OFx1YzViNFx1YWMwMFx1YmE3NFx1YzExYyBcdWJmNTFcdWM1NDRcdWFjMDRcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWFjZTBcdWI5N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjNTQ4IFx1YWNlMFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWM3NTggXHVhYzc4XHVjNzRjXHVjNzc0IFx1YmU2MFx1Yjk3OCBcdWQzYjhcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWFjZmNcdWM3OTAgXHVkNTVjXHViZDA5XHVjOWMwXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMxNFx1YjJlNFx1YmE3NCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWNmY1x1Yzc5MFx1YjI5NCBcdWM4MDhcdWIzMDAgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWI5ZDBcdWI4NWMgXHVkNTU4XHViYTc0LCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjNWYwXHVjMThkXHViNDFjIFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwIFx1ZDVjOFx1YjJjOFx1YmM4NFx1ZDEzMFx1Y2U2OVx1Yzc0NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIEE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMywwMDAsIDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPk4rMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgTSAmbGU7IDEwMCwgMSAmbGU7IEI8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDVjOFx1YjJjOFx1YmM4NFx1ZDEzMFx1Y2U2OVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xMCwgMSwgMTIsIDIsIDgsIDYsIDE0LCA3XHVjNzU4IFx1YzIxY1x1YzExY1x1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDc3NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdyZWVkeSBGb3IgUGllcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxvY2FsIHBpZSBzaG9wIGlzIG9mZmVyaW5nIGEgcHJvbW90aW9uIC0gYWxsLXlvdS1jYW4tZWF0IHBpZXMhIE9idmlvdXNseSwgeW91IGNhbiZyc3F1bzt0IHBhc3MgdXAgdGhpcyBvZmZlci48XC9wPlxyXG5cclxuPHA+VGhlIHNob3AgbGluZXMgdXAgTiBwaWVzIGZyb20gbGVmdCB0byByaWdodCAtIHRoZSBpdGggcGllIGNvbnRhaW5zIEFpIGdyYW1zIG9mIHN1Z2FyLiBBZGRpdGlvbmFsbHksIGFub3RoZXIgTSBwaWVzIGFyZSBwcm92aWRlZCAtIHRoZSBpdGggb2YgdGhlc2UgY29udGFpbnMgQmkgZ3JhbXMgb2Ygc3VnYXIuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZmlyc3QgYWxsb3dlZCB0byBpbnNlcnQgZWFjaCBvZiB0aGUgTSBwaWVzIGZyb20gdGhlIHNlY29uZCBncm91cCBhbnl3aGVyZSBpbnRvIHRoZSBmaXJzdCBsaXN0IG9mIE4gcGllcywgc3VjaCBhcyBhdCBpdHMgc3RhcnQgb3IgZW5kLCBvciBpbiBiZXR3ZWVuIGFueSB0d28gcGllcyBhbHJlYWR5IGluIHRoZSBsaXN0LiBUaGUgcmVzdWx0IHdpbGwgYmUgYSBsaXN0IG9mIE4gKyBNIHBpZXMgd2l0aCB0aGUgY29uc3RyYWludCB0aGF0IHRoZSBpbml0aWFsIE4gcGllcyBhcmUgc3RpbGwgaW4gdGhlaXIgb3JpZ2luYWwgcmVsYXRpdmUgb3JkZXIuPFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyB0aGlzLCB5b3UgYXJlIGFsbG93ZWQgdG8gdGFrZSBvbmUgd2FsayBhbG9uZyB0aGUgbmV3IGxpbmUgb2YgcGllcyBmcm9tIGxlZnQgdG8gcmlnaHQsIHRvIHBpY2sgdXAgeW91ciBzZWxlY3Rpb24gb2YgYWxsLXlvdS1jYW4tZWF0IHBpZXMhIFdoZW4geW91IGFycml2ZSBhdCBhIHBpZSwgeW91IG1heSBjaG9vc2UgdG8gYWRkIGl0IHRvIHlvdXIgcGlsZSwgb3Igc2tpcCBpdC4gSG93ZXZlciwgYmVjYXVzZSB5b3UmcnNxdW87cmUgcmVxdWlyZWQgdG8ga2VlcCBtb3ZpbmcsIGlmIHlvdSBwaWNrIHVwIGEgY2VydGFpbiBwaWUsIHlvdSB3aWxsIG5vdCBiZSBhYmxlIHRvIGFsc28gcGljayB1cCB0aGUgcGllIGltbWVkaWF0ZWx5IGFmdGVyIGl0IChpZiBhbnkpLiBJbiBvdGhlciB3b3JkcywgeW91IGNhbm5vdCBlYXQgY29uc2VjdXRpdmUgcGllcyBpbiB0aGlzIGNvbWJpbmVkIGxpc3QuPFwvcD5cclxuXHJcbjxwPkJlaW5nIGEgcGllIGNvbm5vaXNzZXVyLCB5b3VyIGdvYWwgaXMgdG8gbWF4aW1pemUgdGhlIHRvdGFsIGFtb3VudCBvZiBzdWdhciBpbiB0aGUgcGllcyB5b3UgcGljayB1cCBmcm9tIHRoZSBsaW5lLiBIb3cgbWFueSBncmFtcyBjYW4geW91IGdldD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMzAwMCkuIFRoZSBuZXh0IE4gbGluZXMgY29udGFpbiBvbmUgaW50ZWdlciBBPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgZGVzY3JpYmluZyB0aGUgaW50ZWdlciBudW1iZXIgb2YgZ3JhbXMgb2Ygc3VnYXIgaW4gcGllIGkgaW4gdGhlIGdyb3VwIG9mIE4gcGllcy48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBNICgwICZsZTsgTSAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgcGllcyBpbiB0aGUgc2Vjb25kIGxpc3QuIFRoZSBuZXh0IE0gbGluZXMgY29udGFpbiBvbmUgaW50ZWdlciBCPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEI8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgZGVzY3JpYmluZyB0aGUgaW50ZWdlciBudW1iZXIgb2YgZ3JhbXMgb2Ygc3VnYXIgaW4gcGllIGkgaW4gdGhlIGdyb3VwIG9mIE0gcGllcy48XC9wPlxyXG5cclxuPHA+Rm9yIDIwJSBvZiB0aGUgbWFya3MgZm9yIHRoaXMgcXVlc3Rpb24sIE0gPSAwLiBGb3IgYW5vdGhlciAyMCUgb2YgdGhlIG1hcmtzIGZvciB0aGlzIHF1ZXN0aW9uIE0gPSAxLiBGb3IgYW5vdGhlciAyMCUgb2YgdGhlIG1hcmtzIGZvciB0aGlzIHF1ZXN0aW9uIE0gJmxlOyAxMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGdyYW1zIG9mIHN1Z2FyIGluIGFsbCB0aGUgcGllcyB0aGF0IHlvdSBhcmUgYWJsZSB0byBwaWNrIHVwLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5QbGFjZSB0aGUgcGllcyBpbiB0aGUgb3JkZXI8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+MTAsIDEsIDEyLCAyLCA4LCA2LCAxNCwgNzxcL3A+XHJcblxyXG48cD4odGhhdCBpcywgaW5zZXJ0IHRoZSBwaWUgd2l0aCAxIGdyYW0gb2Ygc3VnYXIgYmV0d2VlbiAxMCBhbmQgMTIsIGFuZCBpbnNlcnQgcGllcyB3aXRoIDIgYW5kIDggZ3JhbXMgb2Ygc3VnYXIsIGluIHRoYXQgb3JkZXIsIGJldHdlZW4gcGllcyAxMiBhbmQgNikuIFRoZW4sIHdlIGNhbiBncmFiIDEwICsgMTIgKyA4ICsgMTQgPSA0NCBncmFtcyBvZiBzdWdhciwgd2hpY2ggaXMgbWF4aW1hbC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Canadian Computing Competition & Olympiad > 2015 > CCC 2015 Senior Division 5번

  • 문제를 번역한 사람: koosaga
  • 잘못된 조건을 찾은 사람: topology