W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
We are given a bar of chocolate composed of 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 and along horizontal lines with . 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 .
Write a program which:
In the first line of the standard input there are two positive integers and separated by a single space, . In the successive lines there are numbers , one per line, . In the successive lines there are numbers , one per line, .
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.
For the input data:
6 4 2 1 3 1 4 4 1 2
the correct result is:
42
Task author: Marcin Kubica.