Description

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.

Input Format

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 Format

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.

2 4 4
1 1 -1 -1
0 10 0 -1
1 -1 1 -1
10 0 -1 0
1 1
2 1
1 2
2 2

122
144
242
244

Hint

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 for supporting this contest.

Resources such as editorials can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5