Problem S. 83. (October 2013)
S. 83. A chocolate bar having N rows, M columns and consisting of identical smaller squares is to be distributed among NM children in a way that everybody gets exactly one square: the chocolate bar lying on the table should be broken into pieces. After we break the bar along a row or a column, the pieces are put back into their original position. However, there is a cost for each breaking: the cost for breaking the chocolate between column i and column i+1 is o_{i}, while the cost for breaking between row j and row j+1 is s_{j}. This rule applies to each individual piece on the table; breaking other separate pieces later (even along the same row or column) will again have the appropriate cost. During the breaking process, every piece stays at their original position, they should not be moved away so that the cost would be less, or should not be stacked on top of each other so that they would be broken simultaneously. Each breaking should take place parallel to the sides of the chocolate bar.
Your program should give the minimal cost for breaking the chocolate into 1x1 squares according to the above rules.
Your program should read the values of M and N (M,N500.000) from the first line of the standard input, then the o_{i} integers from the next M1 lines, finally, the s_{i} integers from the last N1 lines. The minimal cost should appear in the first (and only) line of the standard output.
The example shows a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet''). Explanation: breaking the chocolate bar first along the rows then along the columns, the cost would be s_{1}+s_{2}+s_{3}+4^{.}(o_{1}+o_{2}+o_{3}+o_{4}+o_{5})=7+4^{.}11=51, but this is not optimal.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution; 9 further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time.
Partial points can be obtained according to the following:
 your program yields a solution for M,N5,
 your program yields a solution for M,N50,
 your program yields a solution for M,N500,
 your program yields a solution for M,N1000.
The source code (s83.pas, s83.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s83.txt, s83.pdf, ...)  also describing which developer environment to use for compiling the source  should be submitted in a compressed file s83.zip.
(10 pont)
Deadline expired on 11 November 2013.
Sorry, the solution is available only in Hungarian. Google translation
Mintamegoldásnak Weisz Ambrus megoldását tesszük közzé. S83main.cpp Illetve a dokumentáció: S83megoldas.txt
Statistics:
22 students sent a solution.  
10 points:  Juhász 326 Dániel, Kiss 666 Péter, KovácsDeák Máté, Makk László, Németh 123 Balázs, Weisz Ambrus, Zalavári Márton. 
9 points:  Fonyó Viktória, Gercsó Márk, MolnárSáska Zoltán, Somogyvári Kristóf, Zarándy Álmos. 
6 points:  3 students. 
5 points:  2 students. 
3 points:  1 student. 
1 point:  2 students. 
Unfair, not evaluated:  2 solutions. 
