시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB46314310428.969%

문제

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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBBPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMsMDAwLCAxICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5OKzJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgQjxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IE0gJmxlOyAxMDAsIDEgJmxlOyBCPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1YzhcdWIyYzhcdWJjODRcdWQxMzBcdWNlNjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+MTAsIDEsIDEyLCAyLCA4LCA2LCAxNCwgN1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA3NzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcmVlZHkgRm9yIFBpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBsb2NhbCBwaWUgc2hvcCBpcyBvZmZlcmluZyBhIHByb21vdGlvbiAtIGFsbC15b3UtY2FuLWVhdCBwaWVzISBPYnZpb3VzbHksIHlvdSBjYW4mcnNxdW87dCBwYXNzIHVwIHRoaXMgb2ZmZXIuPFwvcD5cclxuXHJcbjxwPlRoZSBzaG9wIGxpbmVzIHVwIE4gcGllcyBmcm9tIGxlZnQgdG8gcmlnaHQgLSB0aGUgaXRoIHBpZSBjb250YWlucyBBaSBncmFtcyBvZiBzdWdhci4gQWRkaXRpb25hbGx5LCBhbm90aGVyIE0gcGllcyBhcmUgcHJvdmlkZWQgLSB0aGUgaXRoIG9mIHRoZXNlIGNvbnRhaW5zIEJpIGdyYW1zIG9mIHN1Z2FyLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGZpcnN0IGFsbG93ZWQgdG8gaW5zZXJ0IGVhY2ggb2YgdGhlIE0gcGllcyBmcm9tIHRoZSBzZWNvbmQgZ3JvdXAgYW55d2hlcmUgaW50byB0aGUgZmlyc3QgbGlzdCBvZiBOIHBpZXMsIHN1Y2ggYXMgYXQgaXRzIHN0YXJ0IG9yIGVuZCwgb3IgaW4gYmV0d2VlbiBhbnkgdHdvIHBpZXMgYWxyZWFkeSBpbiB0aGUgbGlzdC4gVGhlIHJlc3VsdCB3aWxsIGJlIGEgbGlzdCBvZiBOICsgTSBwaWVzIHdpdGggdGhlIGNvbnN0cmFpbnQgdGhhdCB0aGUgaW5pdGlhbCBOIHBpZXMgYXJlIHN0aWxsIGluIHRoZWlyIG9yaWdpbmFsIHJlbGF0aXZlIG9yZGVyLjxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgdGhpcywgeW91IGFyZSBhbGxvd2VkIHRvIHRha2Ugb25lIHdhbGsgYWxvbmcgdGhlIG5ldyBsaW5lIG9mIHBpZXMgZnJvbSBsZWZ0IHRvIHJpZ2h0LCB0byBwaWNrIHVwIHlvdXIgc2VsZWN0aW9uIG9mIGFsbC15b3UtY2FuLWVhdCBwaWVzISBXaGVuIHlvdSBhcnJpdmUgYXQgYSBwaWUsIHlvdSBtYXkgY2hvb3NlIHRvIGFkZCBpdCB0byB5b3VyIHBpbGUsIG9yIHNraXAgaXQuIEhvd2V2ZXIsIGJlY2F1c2UgeW91JnJzcXVvO3JlIHJlcXVpcmVkIHRvIGtlZXAgbW92aW5nLCBpZiB5b3UgcGljayB1cCBhIGNlcnRhaW4gcGllLCB5b3Ugd2lsbCBub3QgYmUgYWJsZSB0byBhbHNvIHBpY2sgdXAgdGhlIHBpZSBpbW1lZGlhdGVseSBhZnRlciBpdCAoaWYgYW55KS4gSW4gb3RoZXIgd29yZHMsIHlvdSBjYW5ub3QgZWF0IGNvbnNlY3V0aXZlIHBpZXMgaW4gdGhpcyBjb21iaW5lZCBsaXN0LjxcL3A+XHJcblxyXG48cD5CZWluZyBhIHBpZSBjb25ub2lzc2V1ciwgeW91ciBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB0b3RhbCBhbW91bnQgb2Ygc3VnYXIgaW4gdGhlIHBpZXMgeW91IHBpY2sgdXAgZnJvbSB0aGUgbGluZS4gSG93IG1hbnkgZ3JhbXMgY2FuIHlvdSBnZXQ/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMDApLiBUaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gb25lIGludGVnZXIgQTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiksIGRlc2NyaWJpbmcgdGhlIGludGVnZXIgbnVtYmVyIG9mIGdyYW1zIG9mIHN1Z2FyIGluIHBpZSBpIGluIHRoZSBncm91cCBvZiBOIHBpZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTSAoMCAmbGU7IE0gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHBpZXMgaW4gdGhlIHNlY29uZCBsaXN0LiBUaGUgbmV4dCBNIGxpbmVzIGNvbnRhaW4gb25lIGludGVnZXIgQjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBCPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD41PFwvc3VwPiksIGRlc2NyaWJpbmcgdGhlIGludGVnZXIgbnVtYmVyIG9mIGdyYW1zIG9mIHN1Z2FyIGluIHBpZSBpIGluIHRoZSBncm91cCBvZiBNIHBpZXMuPFwvcD5cclxuXHJcbjxwPkZvciAyMCUgb2YgdGhlIG1hcmtzIGZvciB0aGlzIHF1ZXN0aW9uLCBNID0gMC4gRm9yIGFub3RoZXIgMjAlIG9mIHRoZSBtYXJrcyBmb3IgdGhpcyBxdWVzdGlvbiBNID0gMS4gRm9yIGFub3RoZXIgMjAlIG9mIHRoZSBtYXJrcyBmb3IgdGhpcyBxdWVzdGlvbiBNICZsZTsgMTAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIG51bWJlciBvZiBncmFtcyBvZiBzdWdhciBpbiBhbGwgdGhlIHBpZXMgdGhhdCB5b3UgYXJlIGFibGUgdG8gcGljayB1cC48XC9wPlxyXG4iLCJoaW50IjoiPHA+UGxhY2UgdGhlIHBpZXMgaW4gdGhlIG9yZGVyPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjEwLCAxLCAxMiwgMiwgOCwgNiwgMTQsIDc8XC9wPlxyXG5cclxuPHA+KHRoYXQgaXMsIGluc2VydCB0aGUgcGllIHdpdGggMSBncmFtIG9mIHN1Z2FyIGJldHdlZW4gMTAgYW5kIDEyLCBhbmQgaW5zZXJ0IHBpZXMgd2l0aCAyIGFuZCA4IGdyYW1zIG9mIHN1Z2FyLCBpbiB0aGF0IG9yZGVyLCBiZXR3ZWVuIHBpZXMgMTIgYW5kIDYpLiBUaGVuLCB3ZSBjYW4gZ3JhYiAxMCArIDEyICsgOCArIDE0ID0gNDQgZ3JhbXMgb2Ygc3VnYXIsIHdoaWNoIGlzIG1heGltYWwuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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

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