Description

Given two sequences of positive integers, you will play a game with them: you need to perform several operations. In each operation, choose two positive integers $k_1$ and $k_2$, remove the last $k_1$ numbers of the first sequence and compute their sum $s_1$; remove the last $k_2$ numbers of the second sequence and compute their sum $s_2$. The score of this operation is $(s_2-k_2)\times(s_1-k_1)$. Both sequences must become empty at the same time; it is not allowed for one sequence to be empty while the other still contains numbers. The total score of the game is the sum of the scores of all operations.

Find the minimum possible total score.

Input Format

The first line contains two integers $n$ and $m$, the initial lengths of the first and second sequences, respectively.

The second line contains $n$ positive integers, the numbers of the first sequence.

The third line contains $m$ positive integers, the numbers of the second sequence.

All numbers in the sequences are at most $1000$.

Output Format

Output a single integer, the minimum total score.

3 2
1 2 3 
1 2 

2

Hint

• For $20\%$ of the testdata, $n, m \le 20$.
• For $40\%$ of the testdata, $n, m \le 200$.
• For $100\%$ of the testdata, $n, m \le 2000$.

Translated by ChatGPT 5