시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 160 47 23 20.354%

문제

양의 정수로 구성된 길이 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+XHJcbjxwPlx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMSgmZ2U7MSlcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBTMVx1Yzc3NFx1Yjc3YyBcdWQ1NThcdWFjZTAsIFx1YzIxOFx1YzVmNCBCXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMigmZ2U7MSlcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBTMlx1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWMyMThcdWM1ZjQgXHVjODA0XHVjY2I0XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCAoUzEgLSBLMSkmdGltZXM7KFMyIC0gSzIpXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWMyMThcdWI0ZTRcdWM3NDQgXHVjNmQwXHViNzk4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjMjE4XHVjNWY0IEFcdWM3NTggXHViNGE0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIEsxXHVhYzFjXHVjNzU4IFx1YzIxOFx1YjRlNFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWFjZTAsIFx1YzIxOFx1YzVmNCBCXHVjNzU4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBLMlx1YWMxY1x1Yzc1OCBcdWMyMThcdWI0ZTRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzIxOFx1YzVmNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NDAgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWI0MTBcdWM3NDQgXHViNTRjIFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTg4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWM4MDRcdWNjYjQgXHVjODEwXHVjMjE4XHViMjk0LCBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkMWQgXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzgwNFx1Y2NiNCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbjxwPlx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWMyMThcdWI0ZTRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTYwIFx1YjU0YyAxXHVhYzFjIFx1Yzc3NFx1YzBjMVx1YzUyOSBcdWM4MWNcdWFjNzBcdWI5N2MgXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwXHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YzgxY1x1YWM3MFx1YjQxMFx1Yzc0NCBcdWI1NGMgXHViMDVkXHViMDljXHViMmU0LiBcdWM5ODksIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzgxY1x1YWM3MFx1YjQxMFx1YjI5NFx1YjM3MCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjA5YyBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM5ODksIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWI5Y2MgXHViMGE4XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE4sIE0oMSZsZTtOLCBNJmxlOzIsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgQVx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YzU1ZVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IEJcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIDEsMDAwXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MDRcdWNjYjQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIEl2YW4gbGlrZXMgdG8gcGxheSBnYW1lcyBpbiBoaXMgc3BhcmUgdGltZS4gVW5mb3J0dW5hdGVseSwgaGUgY2Fubm90IGFsd2F5cyBlbmpveSB0aGUgY29tcGFueSBvZiBoaXMgZnJpZW5kcyBhbmQgc29tZXRpbWVzIGhlIGlzIGEgbGl0dGxlIGJvcmVkIHdoZW4gaGUgaXMgYWxvbmUuIFRoZXJlZm9yZSwgaGUgbWFrZXMgdXAgZ2FtZXMsIHdoZXJlIGhlIGlzIHRoZSBvbmx5IHBsYXllci4gSGUgaXMgZXNwZWNpYWxseSBwcm91ZCBvZiBoaXMgbGFzdCBnYW1lIGFuZCBsaWtlcyB0byB0ZWxsIHlvdSBhYm91dCBpdC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0d28gZmluaXRlIHNlcXVlbmNlcyBvZiBwb3NpdGl2ZSBpbnRlZ2Vycy4gVGhlIGdhbWUgY29uc2lzdHMgb2YgbWFraW5nIGNvbnNlY3V0aXZlIG1vdmVzLiBZb3UgYXJlIGFsbG93ZWQgdG8gbWFrZSB0aGUgZm9sbG93aW5nIG1vdmUuIFlvdSByZW1vdmUgdGhlIGxhc3QgSzEgbnVtYmVycyAoSzEmZ2U7MSkgZnJvbSB0aGUgZmlyc3Qgc2VxdWVuY2UgKHBvc3NpYmx5IHRoZSB3aG9sZSBzZXF1ZW5jZSkgYW5kIGZpbmQgdGhlaXIgc3VtIFMxIGFuZCB0aGUgbGFzdCBLMiBudW1iZXJzIChLMiZnZTsxKSBmcm9tIHRoZSBzZWNvbmQgc2VxdWVuY2UgKGFnYWluIHlvdSBjYW4gcmVtb3ZlIHRoZSB3aG9sZSBzZXF1ZW5jZSkgYW5kIGZpbmQgdGhlaXIgc3VtIFMyLiBUaGVuIHlvdSBjYWxjdWxhdGUgdGhlIGNvc3Qgb2YgdGhlIG1vdmUgdG8gYmUgKFMxICZuZGFzaDsgSzEpKihTMiAmbmRhc2g7IEsyKS4gWW91IGNvbnRpbnVlIHRvIG1ha2UgbW92ZXMgdW50aWwgeW91IHJlbW92ZSBhbGwgdGhlIG51bWJlcnMgaW4gYm90aCBzZXF1ZW5jZXMuIFRoZSB0b3RhbCBjb3N0IG9mIHRoZSBnYW1lIGlzIHRoZSBzdW0gb2YgdGhlIGNvc3RzIG9mIGFsbCBtb3Zlcy4gWW91ciBnb2FsIGlzIHRvIG1pbmltaXplIHRoaXMgdG90YWwgY29zdC4gWW91IGFyZSBub3QgYWxsb3dlZCB0byBsZWF2ZSBvbmUgb2YgdGhlIHNlcXVlbmNlcyBlbXB0eSwgd2hpbGUgdGhlIG90aGVyIGlzIG5vdC48XC9wPlxyXG5cclxuPHA+QXMgSXZhbiBoYXMgdG9sZCB5b3UgdGhlIHJ1bGVzIG9mIHRoZSBnYW1lLCB5b3UgcmVhbGl6ZSB0aGF0IGl0IGlzIGVhc2lseSBzb2x2YWJsZSB3aXRoIHRoZSBoZWxwIG9mIGEgY29tcHV0ZXIsIHNvIHlvdSBkZWNpZGUgdG8gd3JpdGUgYSBwcm9ncmFtIEdBTUUsIHRoYXQgY29tcHV0ZXMgdGhlIG1pbmltdW0gdG90YWwgY29zdCBvZiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGRhdGEgaXMgcmVhZCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBhbmQgY29uc2lzdHMgb2YgdGhyZWUgbGluZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIEwxIGFuZCBMMiAoMSAmbGU7IEwxLCBMMiAmbGU7IDIwMDApLCB3aGljaCBkZW5vdGUgdGhlIGxlbmd0aHMgb2YgdGhlIHR3byBzZXF1ZW5jZXMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBMMSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHdoaWNoIGFyZSB0aGUgZWxlbWVudHMgb2YgdGhlIGZpcnN0IHNlcXVlbmNlLiBUaGUgdGhpcmQgbGluZSBjb250YWlucyBMMiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHdoaWNoIGFyZSB0aGUgZWxlbWVudHMgb2YgdGhlIHNlY29uZCBzZXF1ZW5jZS4gVGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZXMgZG8gbm90IGV4Y2VlZCAxMDAwLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaGFzIHRvIG91dHB1dCBvbmUgbGluZSBvbiB0aGUgc3RhbmRhcmQgb3V0cHV0IHRoYXQgY29udGFpbnMgb25seSBvbmUgbnVtYmVyICZuZGFzaDsgdGhlIG1pbmltdW0gdG90YWwgY29zdCBvZiB0aGUgZ2FtZSBhcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==