
X Olympiad in Informatics 2002/2003

Problem: Chocolate

Author: Marcin Kubica

We are given a bar of chocolate composed of m*n square
pieces. One should break the chocolate into single squares. Parts of
the chocolate may be broken along the vertical and horizontal lines as
indicated by the broken lines in the picture. A single break of a
part of the chocolate along a chosen vertical or horizontal line
divides that part into two smaller ones. Each break of a part of
the chocolate is charged a cost expressed by a positive
integer. This cost does not depend on the size of the part that is
being broken but only depends on the line the break goes along. Let
us denote the costs of breaking along consecutive vertical lines with
x_{1}, x_{2}, ...,
x_{m1} and along horizontal lines with
y_{1}, y_{2}, ...,
y_{n1}. The cost of breaking the whole bar into
single squares is the sum of the successive breaks. One should
compute the minimal cost of breaking the whole chocolate into single
single squares. For example, if we break the chocolate presented
in the picture first along the horizontal lines, and next each
obtained part along vertical lines then the cost of that breaking will
be
y_{1}+y_{2}+y_{3}+4*(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}).
Task
Write a program which:
 reads the numbers x_{1}, x_{2}, ...,
x_{m1} and y_{1},
y_{2}, ..., y_{n1},
 computes the minimal cost of breaking the whole chocolate into single squares,
 writes the result.
Input
In the first line of the standard input there are two positive
integers m and n separated by a single space, 2 <=
m,n <= 1000. In the successive m1 lines there
are numbers x_{1}, x_{2}, ...,
x_{m1}, one per line, 1 <=
x_{i} <= 1000. In the successive n1 lines there
are numbers y_{1}, y_{2}, ...,
y_{n1}, one per line, 1 <=
y_{i} <= 1000.
Output
Your program should write to the standard output. In the first and
only line your program should write one integer  the minimal cost of
breaking the whole chocolate into single squares.
Example
For the following input data:
6 4
2
1
3
1
4
4
1
2
the correct answer is in the following output:
42
Print friendly version
