P5449 [THUPC 2018] Recruitment Notice for Junior Teaching Assistants of "Algorithms and Data Structures"

University T and University U are the two best universities in Country W. "Algorithms and Data Structures" is a classic course at University U, and it has won the honor of "University U First-Class Premium Course" for more than one hundred consecutive years. Little O is the TA for this course next year. Because the course is too popular, he cannot handle it alone, so he is recruiting junior teaching assistants for this course. However, the recruitment requirements are a bit strange...

The content of the course "Algorithms and Data Structures" is divided into $n$ knowledge points, and each knowledge point has $m$ corresponding practice problems. Each problem has two attribute values: the $j$-th practice problem of the $i$-th knowledge point can increase the algorithm ability of the student who solves it by $a_{i, j}$, and increase the data structure ability by $d_{i, j}$. These attribute values are all integers, but they may be negative, and there may even be practice problems where both attributes are negative. (Do not ask how such problems got into the problem set...) There are $q$ students registered for next year's "Algorithms and Data Structures" course. By examining each student's previous learning situation, Little O decides to teach each student according to their aptitude. Specifically, for the $k$-th student and the $i$-th knowledge point, Little O wants this student to complete exactly $c_{k, i}$ practice problems of this knowledge point. In fact, Little O has close ties with University T and wants to stir up some trouble at University U. For each student, let the total improvements in algorithm ability and data structure ability from all selected practice problems be $A$ and $D$, respectively. Little O's goal is to maximize $A^2 + D^2$. In this way, no matter how much the student's abilities increase or decrease in either aspect, it is what Little O wants. Please compute the maximum value of this objective for each student.

Each input file contains only one testdata. * The first line contains three positive integers $n, m, q$. * The next $n$ lines each contain $m$ integers; in the $i$-th of these lines, the $j$-th integer is $a_{i, j}$. * The next $n$ lines each contain $m$ integers; in the $i$-th of these lines, the $j$-th integer is $d_{i, j}$. * The next $q$ lines each contain $n$ integers; in the $k$-th of these lines, the $i$-th integer is $c_{k, i}$. For each line of input, if multiple numbers are given, then adjacent numbers are separated by exactly one space.

Output $q$ lines, each with 1 integer: the integer on line $k$ is the maximum value of $A^2 + D^2$ for the $k$-th student.

### Sample Explanation There are 2 knowledge points, and each knowledge point has 4 practice problems; there are 4 students. Take the 2nd student as an example. We need to select exactly 2 practice problems from the 1st knowledge point and exactly 1 practice problem from the 2nd knowledge point for this student. One optimal plan is to choose the 1st and 3rd problems in the 1st knowledge point, and choose the 1st problem in the 2nd knowledge point. The improvement in algorithm ability from these problems is $A = a_{1,1} + a_{1,3} + a_{2,1} = 1 + (-1) + 0 = 0$, and the improvement in data structure ability is $D = d_{1,1} + d_{1,3} + d_{2,1} = 1 + 1 + 10 = 12$. Then $A^2 + D^2 = 144$, and there is no better plan. ### Constraints $1 \leq n \leq 6$, $1 \leq m \leq 666$, $1 \leq q \leq 666$, and all $a_{i, j}$ and $d_{i, j}$ are in the range $[-10^9, 10^9]$. For the final testdata, all $c_{k, i}$ are generated independently and uniformly at random in the range $[0, m]$. ### Hint Each output number may be very large, and may even exceed the range of 64-bit integers. * In C++, you can use the `__int128_t` type to represent signed 128-bit integers, or use `__uint128_t` to represent unsigned 128-bit integers. These two data types cannot be directly used for input/output. * In Java, you can use the `BigInteger` class. ### Copyright Information From the 2018 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2018). Thanks to [Pony.ai](http://pony.ai/) for supporting this contest. Resources such as editorials can be found at . Translated by ChatGPT 5