시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 142 44 20 21.053%

문제

양의 정수로 구성된 길이 N인 수열 A와 길이 M인 수열 B가 있다. 두 수열에 대해서 게임을 진행하려 한다.

수열 A의 뒤에서부터 K1(≥1)개의 수들의 합을 S1이라 하고, 수열 B의 뒤에서부터 K2(≥1)개의 수들의 합을 S2라 하자. 한 개의 수를 선택할 수도 있고, 수열 전체를 선택할 수도 있다. 이 단계에서의 점수는 (S1 - K1)×(S2 - K2)가 된다. 이 때 선택한 수들을 원래 수열에서 제거한다. 즉, 수열 A의 뒤에서부터 K1개의 수들을 제거하고, 수열 B의 뒤에서부터 K2개의 수들을 제거한다. 그리고 남아있는 수열에 대해서 같은 방식으로 게임을 진행한다. 게임은 두 수열을 이루는 수들이 모두 제거됐을 때 끝난다. 이와 같이 게임을 진행했을 때의 전체 점수는, 각 단계에서의 점수의 총 합이 된다.

두 수열이 주어졌을 때, 전체 점수의 최소를 구하는 프로그램을 작성하시오.

수열에서 수들을 제거할 때 1개 이상씩 제거를 하게 된다. 또한 게임은 두 수열을 이루는 수들이 모두 제거됐을 때 끝난다. 즉, 하나의 수열은 모두 제거됐는데 다른 하나의 수열은 모두 제거되지 않은 경우는 게임이 끝난 경우가 아니다. 즉, 하나의 수열만 남게 되는 경우가 있어서는 안된다.

입력

첫째 줄에 두 정수 N, M(1≤N, M≤2,000)이 주어진다. 다음 줄에는 A를 이루는 수들이 앞에서부터 주어진다. 그 다음 줄에는 B를 이루는 수들이 앞에서부터 주어진다. 두 수열을 이루는 수들은 모두 1,000이하이다.

출력

첫째 줄에 전체 점수의 최소값을 출력한다.

예제 입력 1

3 2
1 2 3
1 2

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIxOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWFlMzhcdWM3NzQgTlx1Yzc3OCBcdWMyMThcdWM1ZjQgQVx1YzY0MCBcdWFlMzhcdWM3NzQgTVx1Yzc3OCBcdWMyMThcdWM1ZjQgQlx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMSgmZ2U7MSlcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBTMVx1Yzc3NFx1Yjc3YyBcdWQ1NThcdWFjZTAsIFx1YzIxOFx1YzVmNCBCXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMigmZ2U7MSlcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBTMlx1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWMyMThcdWM1ZjQgXHVjODA0XHVjY2I0XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCAoUzEgLSBLMSkmdGltZXM7KFMyIC0gSzIpXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzZkMFx1Yjc5OCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMVx1YWMxY1x1Yzc1OCBcdWMyMThcdWI0ZTRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTU4XHVhY2UwLCBcdWMyMThcdWM1ZjQgQlx1Yzc1OCBcdWI0YTRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgSzJcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHViNDEwXHVjNzQ0IFx1YjU0YyBcdWIwNWRcdWIwOWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVjODA0XHVjY2I0IFx1YzgxMFx1YzIxOFx1YjI5NCwgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExY1x1Yzc1OCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4MDRcdWNjYjQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG48cD5cdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWI1NGMgMVx1YWMxYyBcdWM3NzRcdWMwYzFcdWM1MjkgXHVjODFjXHVhYzcwXHViOTdjIFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWFjOGNcdWM3ODRcdWM3NDAgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWI0MTBcdWM3NDQgXHViNTRjIFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVjOTg5LCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWI0MTBcdWIyOTRcdWIzNzAgXHViMmU0XHViOTc4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzgxY1x1YWM3MFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjOTg5LCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHVjNWY0XHViOWNjIFx1YjBhOFx1YWM4YyBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YzViNFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBOLCBNKDEmbGU7TiwgTSZsZTsyLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IEFcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBCXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCAxLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODA0XHVjY2I0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjE5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBJdmFuIGxpa2VzIHRvIHBsYXkgZ2FtZXMgaW4gaGlzIHNwYXJlIHRpbWUuIFVuZm9ydHVuYXRlbHksIGhlIGNhbm5vdCBhbHdheXMgZW5qb3kgdGhlIGNvbXBhbnkgb2YgaGlzIGZyaWVuZHMgYW5kIHNvbWV0aW1lcyBoZSBpcyBhIGxpdHRsZSBib3JlZCB3aGVuIGhlIGlzIGFsb25lLiBUaGVyZWZvcmUsIGhlIG1ha2VzIHVwIGdhbWVzLCB3aGVyZSBoZSBpcyB0aGUgb25seSBwbGF5ZXIuIEhlIGlzIGVzcGVjaWFsbHkgcHJvdWQgb2YgaGlzIGxhc3QgZ2FtZSBhbmQgbGlrZXMgdG8gdGVsbCB5b3UgYWJvdXQgaXQuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdHdvIGZpbml0ZSBzZXF1ZW5jZXMgb2YgcG9zaXRpdmUgaW50ZWdlcnMuIFRoZSBnYW1lIGNvbnNpc3RzIG9mIG1ha2luZyBjb25zZWN1dGl2ZSBtb3Zlcy4gWW91IGFyZSBhbGxvd2VkIHRvIG1ha2UgdGhlIGZvbGxvd2luZyBtb3ZlLiBZb3UgcmVtb3ZlIHRoZSBsYXN0IEsxIG51bWJlcnMgKEsxJmdlOzEpIGZyb20gdGhlIGZpcnN0IHNlcXVlbmNlIChwb3NzaWJseSB0aGUgd2hvbGUgc2VxdWVuY2UpIGFuZCBmaW5kIHRoZWlyIHN1bSBTMSBhbmQgdGhlIGxhc3QgSzIgbnVtYmVycyAoSzImZ2U7MSkgZnJvbSB0aGUgc2Vjb25kIHNlcXVlbmNlIChhZ2FpbiB5b3UgY2FuIHJlbW92ZSB0aGUgd2hvbGUgc2VxdWVuY2UpIGFuZCBmaW5kIHRoZWlyIHN1bSBTMi4gVGhlbiB5b3UgY2FsY3VsYXRlIHRoZSBjb3N0IG9mIHRoZSBtb3ZlIHRvIGJlIChTMSAmbmRhc2g7IEsxKSooUzIgJm5kYXNoOyBLMikuIFlvdSBjb250aW51ZSB0byBtYWtlIG1vdmVzIHVudGlsIHlvdSByZW1vdmUgYWxsIHRoZSBudW1iZXJzIGluIGJvdGggc2VxdWVuY2VzLiBUaGUgdG90YWwgY29zdCBvZiB0aGUgZ2FtZSBpcyB0aGUgc3VtIG9mIHRoZSBjb3N0cyBvZiBhbGwgbW92ZXMuIFlvdXIgZ29hbCBpcyB0byBtaW5pbWl6ZSB0aGlzIHRvdGFsIGNvc3QuIFlvdSBhcmUgbm90IGFsbG93ZWQgdG8gbGVhdmUgb25lIG9mIHRoZSBzZXF1ZW5jZXMgZW1wdHksIHdoaWxlIHRoZSBvdGhlciBpcyBub3QuPFwvcD5cclxuXHJcbjxwPkFzIEl2YW4gaGFzIHRvbGQgeW91IHRoZSBydWxlcyBvZiB0aGUgZ2FtZSwgeW91IHJlYWxpemUgdGhhdCBpdCBpcyBlYXNpbHkgc29sdmFibGUgd2l0aCB0aGUgaGVscCBvZiBhIGNvbXB1dGVyLCBzbyB5b3UgZGVjaWRlIHRvIHdyaXRlIGEgcHJvZ3JhbSBHQU1FLCB0aGF0IGNvbXB1dGVzIHRoZSBtaW5pbXVtIHRvdGFsIGNvc3Qgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBkYXRhIGlzIHJlYWQgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgYW5kIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBMMSBhbmQgTDIgKDEgJmxlOyBMMSwgTDIgJmxlOyAyMDAwKSwgd2hpY2ggZGVub3RlIHRoZSBsZW5ndGhzIG9mIHRoZSB0d28gc2VxdWVuY2VzLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTDEgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCB3aGljaCBhcmUgdGhlIGVsZW1lbnRzIG9mIHRoZSBmaXJzdCBzZXF1ZW5jZS4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgTDIgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCB3aGljaCBhcmUgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZWNvbmQgc2VxdWVuY2UuIFRoZSBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2VzIGRvIG5vdCBleGNlZWQgMTAwMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGhhcyB0byBvdXRwdXQgb25lIGxpbmUgb24gdGhlIHN0YW5kYXJkIG91dHB1dCB0aGF0IGNvbnRhaW5zIG9ubHkgb25lIG51bWJlciAmbmRhc2g7IHRoZSBtaW5pbXVtIHRvdGFsIGNvc3Qgb2YgdGhlIGdhbWUgYXMgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=