Minimum Game Score Partitioning

You are given two sequences of positive integers, (A) and (B). You need to play a game with them by performing a sequence of operations. In each operation, you must choose two positive integers (k_1) and (k_2). Then, you remove the last (k_1) elements from sequence (A) and compute their sum (s_1), and remove the last (k_2) elements from sequence (B) and compute their sum (s_2). The score obtained from this operation is [ \bigl(s_2 - k_2\bigr)\times \bigl(s_1 - k_1\bigr). ] The rule is that both sequences must be emptied simultaneously; you cannot empty one sequence while the other still has elements. The total score of the game is the sum of the scores of all operations. Your task is to find the minimum possible total score achievable by optimally choosing the values (k_1) and (k_2) in each operation.

Note: The game is equivalent to partitioning the first sequence into several consecutive segments and the second sequence into the same number of consecutive segments. For each corresponding pair of segments, if the segment from (A) has length (\ell_1) and sum (S_1), and the segment from (B) has length (\ell_2) and sum (S_2), then the contribution to the total score is [ (S_1-\ell_1)\times (S_2-\ell_2). ] The objective is to minimize the sum of these products.

inputFormat

The input consists of three lines:

1. The first line contains two positive integers \(n\) and \(m\) denoting the lengths of the two sequences \(A\) and \(B\) respectively.
2. The second line contains \(n\) positive integers representing the sequence \(A\).
3. The third line contains \(m\) positive integers representing the sequence \(B\).

You may assume that \(1 \leq n, m \leq 50\) so that an \(O(n^2 \cdot m^2)\) solution is acceptable.

outputFormat

Output a single integer, the minimum total score achievable.

sample

1 1
2
3

2