Two Sequences

You are given a sequence A of length N and a sequence B of length M. Every element is a positive integer. A game is played with these two sequences.

In one step, choose K1 elements (K1 >= 1) from the end of the current sequence A, and choose K2 elements (K2 >= 1) from the end of the current sequence B. Let S1 be the sum of the chosen elements from A, and let S2 be the sum of the chosen elements from B. The score for this step is (S1 - K1) x (S2 - K2). Then remove the chosen elements from their sequences.

Repeat this process until all elements of both sequences have been removed. The total score is the sum of the scores from all steps.

Each step must remove at least one element from each sequence. Therefore, it is not allowed for one sequence to become empty while the other sequence still has elements remaining.

Given the two sequences, find the minimum possible total score.

The first line contains two integers N and M (1 <= N, M <= 2,000).

The second line contains the elements of sequence A in order from front to back.

The third line contains the elements of sequence B in order from front to back.

All elements of both sequences are positive integers not greater than 1,000.

Print the minimum possible total score on the first line.