Maximizing Skill Improvement

In the Algorithms and Data Structures course, the material is divided into \(n\) knowledge points. For each knowledge point there are \(m\) practice problems. The \(j\)th problem of the \(i\)th knowledge point improves a student’s algorithm skills by \(a_{i,j}\) and data structure skills by \(d_{i,j}\). Note that these integer values can be negative (even both simultaneously).

For the next academic year, \(q\) students have registered. After assessing each student’s previous performance, the instructor assigns personalized requirements. Specifically, for the \(k\)th student and the \(i\)th knowledge point, the student must complete exactly \(c_{k,i}\) problems from that knowledge point.

Let the total improvement in algorithm and data structure skills for a student be \(A\) and \(D\) respectively, i.e., the sums of the corresponding \(a\) and \(d\) values over all chosen problems. The objective is to maximize \[ A^2 + D^2, \] which favors choices that yield a large absolute change in skills in any direction.

For each student, compute the maximum achievable value of \(A^2+D^2\) under the constraint that, for every knowledge point \(i\), exactly \(c_{k,i}\) problems are chosen from the \(m\) available.

inputFormat

The input begins with three integers \(n\), \(m\), and \(q\) (the number of knowledge points, the number of problems per knowledge point, and the number of students respectively).

This is followed by \(n\) lines, each containing \(m\) integers representing \(a_{i,1}, a_{i,2}, \dots, a_{i,m}\) for knowledge point \(i\).

After that, there are \(n\) lines, each with \(m\) integers representing \(d_{i,1}, d_{i,2}, \dots, d_{i,m}\) for knowledge point \(i\).

Then, there are \(q\) lines. The \(k\)th of these lines contains \(n\) integers \(c_{k,1}, c_{k,2}, \dots, c_{k,n}\), where \(c_{k,i}\) is the number of problems the \(k\)th student must complete from knowledge point \(i\>.

outputFormat

For each student, output a single integer: the maximum possible value of \(A^2+D^2\) that can be achieved by selecting the required number of practice problems for each knowledge point.

sample

1 3 1
1 -2 3
2 5 -1
2

50