시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 93 17 12 15.584%

문제

양의 정수로 구성된 길이 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이하이다.

출력

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

예제 입력

3 2
1 2 3
1 2

예제 출력

2

힌트