시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB248804827.119%

문제

양의 정수로 구성된 길이 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+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWI0YTRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgSzxzdWI+MTxcL3N1Yj4oJmdlOyAxKVx1YWMxY1x1Yzc1OCBcdWMyMThcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzQ0IFM8c3ViPjE8XC9zdWI+XHVjNzc0XHViNzdjIFx1ZDU1OFx1YWNlMCwgXHVjMjE4XHVjNWY0IEJcdWM3NTggXHViNGE0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIEs8c3ViPjI8XC9zdWI+KCZnZTsgMSlcdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBTPHN1Yj4yPFwvc3ViPlx1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWMyMThcdWM1ZjQgXHVjODA0XHVjY2I0XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCAoUzxzdWI+MTxcL3N1Yj4gLSBLPHN1Yj4xPFwvc3ViPikgJnRpbWVzOyAoUzxzdWI+MjxcL3N1Yj4gLSBLPHN1Yj4yPFwvc3ViPilcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzIxOFx1YjRlNFx1Yzc0NCBcdWM2ZDBcdWI3OTggXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWI0YTRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgSzxzdWI+MTxcL3N1Yj5cdWFjMWNcdWM3NTggXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YWNlMCwgXHVjMjE4XHVjNWY0IEJcdWM3NTggXHViNGE0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIEs8c3ViPjI8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YzIxOFx1YjRlNFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YzgxY1x1YWM3MFx1YjQxMFx1Yzc0NCBcdWI1NGMgXHViMDVkXHViMDljXHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjXHVjNzU4IFx1YzgwNFx1Y2NiNCBcdWM4MTBcdWMyMThcdWIyOTQsIFx1YWMwMSBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWNcdWM3NTggXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2QxZCBcdWQ1NjlcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzgwNFx1Y2NiNCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjMjE4XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU2MCBcdWI1NGMgMVx1YWMxYyBcdWM3NzRcdWMwYzFcdWM1MjkgXHVjODFjXHVhYzcwXHViOTdjIFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWFjOGNcdWM3ODRcdWM3NDAgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWI0MTBcdWM3NDQgXHViNTRjIFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVjOTg5LCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM4MWNcdWFjNzBcdWI0MTBcdWIyOTRcdWIzNzAgXHViMmU0XHViOTc4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzgxY1x1YWM3MFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjOTg5LCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHVjNWY0XHViOWNjIFx1YjBhOFx1YWM4YyBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YzViNFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE4sIE0oMSAmbGU7IE4sIE0gJmxlOyAyLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IEFcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBCXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCAxLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgwNFx1Y2NiNCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIEl2YW4gbGlrZXMgdG8gcGxheSBnYW1lcyBpbiBoaXMgc3BhcmUgdGltZS4gVW5mb3J0dW5hdGVseSwgaGUgY2Fubm90IGFsd2F5cyBlbmpveSB0aGUgY29tcGFueSBvZiBoaXMgZnJpZW5kcyBhbmQgc29tZXRpbWVzIGhlIGlzIGEgbGl0dGxlIGJvcmVkIHdoZW4gaGUgaXMgYWxvbmUuIFRoZXJlZm9yZSwgaGUgbWFrZXMgdXAgZ2FtZXMsIHdoZXJlIGhlIGlzIHRoZSBvbmx5IHBsYXllci4gSGUgaXMgZXNwZWNpYWxseSBwcm91ZCBvZiBoaXMgbGFzdCBnYW1lIGFuZCBsaWtlcyB0byB0ZWxsIHlvdSBhYm91dCBpdC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0d28gZmluaXRlIHNlcXVlbmNlcyBvZiBwb3NpdGl2ZSBpbnRlZ2Vycy4gVGhlIGdhbWUgY29uc2lzdHMgb2YgbWFraW5nIGNvbnNlY3V0aXZlIG1vdmVzLiBZb3UgYXJlIGFsbG93ZWQgdG8gbWFrZSB0aGUgZm9sbG93aW5nIG1vdmUuIFlvdSByZW1vdmUgdGhlIGxhc3QgSzEgbnVtYmVycyAoSzEmZ2U7MSkgZnJvbSB0aGUgZmlyc3Qgc2VxdWVuY2UgKHBvc3NpYmx5IHRoZSB3aG9sZSBzZXF1ZW5jZSkgYW5kIGZpbmQgdGhlaXIgc3VtIFMxIGFuZCB0aGUgbGFzdCBLMiBudW1iZXJzIChLMiZnZTsxKSBmcm9tIHRoZSBzZWNvbmQgc2VxdWVuY2UgKGFnYWluIHlvdSBjYW4gcmVtb3ZlIHRoZSB3aG9sZSBzZXF1ZW5jZSkgYW5kIGZpbmQgdGhlaXIgc3VtIFMyLiBUaGVuIHlvdSBjYWxjdWxhdGUgdGhlIGNvc3Qgb2YgdGhlIG1vdmUgdG8gYmUgKFMxICZuZGFzaDsgSzEpKihTMiAmbmRhc2g7IEsyKS4gWW91IGNvbnRpbnVlIHRvIG1ha2UgbW92ZXMgdW50aWwgeW91IHJlbW92ZSBhbGwgdGhlIG51bWJlcnMgaW4gYm90aCBzZXF1ZW5jZXMuIFRoZSB0b3RhbCBjb3N0IG9mIHRoZSBnYW1lIGlzIHRoZSBzdW0gb2YgdGhlIGNvc3RzIG9mIGFsbCBtb3Zlcy4gWW91ciBnb2FsIGlzIHRvIG1pbmltaXplIHRoaXMgdG90YWwgY29zdC4gWW91IGFyZSBub3QgYWxsb3dlZCB0byBsZWF2ZSBvbmUgb2YgdGhlIHNlcXVlbmNlcyBlbXB0eSwgd2hpbGUgdGhlIG90aGVyIGlzIG5vdC48XC9wPlxyXG5cclxuPHA+QXMgSXZhbiBoYXMgdG9sZCB5b3UgdGhlIHJ1bGVzIG9mIHRoZSBnYW1lLCB5b3UgcmVhbGl6ZSB0aGF0IGl0IGlzIGVhc2lseSBzb2x2YWJsZSB3aXRoIHRoZSBoZWxwIG9mIGEgY29tcHV0ZXIsIHNvIHlvdSBkZWNpZGUgdG8gd3JpdGUgYSBwcm9ncmFtIEdBTUUsIHRoYXQgY29tcHV0ZXMgdGhlIG1pbmltdW0gdG90YWwgY29zdCBvZiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGRhdGEgaXMgcmVhZCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBhbmQgY29uc2lzdHMgb2YgdGhyZWUgbGluZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIEwxIGFuZCBMMiAoMSAmbGU7IEwxLCBMMiAmbGU7IDIwMDApLCB3aGljaCBkZW5vdGUgdGhlIGxlbmd0aHMgb2YgdGhlIHR3byBzZXF1ZW5jZXMuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBMMSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHdoaWNoIGFyZSB0aGUgZWxlbWVudHMgb2YgdGhlIGZpcnN0IHNlcXVlbmNlLiBUaGUgdGhpcmQgbGluZSBjb250YWlucyBMMiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHdoaWNoIGFyZSB0aGUgZWxlbWVudHMgb2YgdGhlIHNlY29uZCBzZXF1ZW5jZS4gVGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZXMgZG8gbm90IGV4Y2VlZCAxMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBoYXMgdG8gb3V0cHV0IG9uZSBsaW5lIG9uIHRoZSBzdGFuZGFyZCBvdXRwdXQgdGhhdCBjb250YWlucyBvbmx5IG9uZSBudW1iZXIgJm5kYXNoOyB0aGUgbWluaW11bSB0b3RhbCBjb3N0IG9mIHRoZSBnYW1lIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d