题目背景

T 大学和 U 大学是 W 国最好的两个大学。《算法与数据结构》是 U 大学的一门经典课程，曾连续百余年获得“U 大学一级精品课程”的荣誉。

小 O 是这门课明年的助教。由于这门课过于火爆，他一个人忙不过来，所以他正在招募这门课的小助教。不过，招募的条件有点奇怪……

题目描述

《算法与数据结构》课程的内容共分为 $n$ 个知识点，而每个知识点均有配套的的 $m$ 道练习题。每道题有两个属性值，第 $i$ 个知识点的第 $j$ 道练习题可以让做这道题的学生的算法能力提高 $a_{i, j}$，数据结构能力提高 $d_{i, j}$。这些属性值均为整数，但是可能为负数，甚至可能存在两个属性均为负的练习题。（不要问这种题是怎么被加进题库的…）

明年的《算法与数据结构》课共有 $q$ 个学生注册。通过对每个学生以前学习情况的考察，小 O 决定对每个学生进行“因材施教”。具体方法是，对于第 $k$ 个学生、第 $i$ 个知识点，小 O 希望这个学生完成这个知识点的恰好 $c_{k, i}$ 道练习题。

其实小 O 和 T 大学关系密切，希望在 U 大学搞点事情。对于每个学生，设为该学生选出的所有练习题对于算法能力与数据结构能力的提升分别为 $A$ 与 $D$，小 O 的目标是最大化 $A^2+D^2$，这样无论这个学生在哪个方面能力提升或降低的程度很大，都是小 O 所期望的。

请对于每个学生计算这个目标的最大值。

输入格式

每个输入文件仅包含一个测试数据。

• 第一行包含三个正整数 $n, m, q$。

• 接下来 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个整数为 $a_{i, j}$。

• 接下来 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个整数为 $d_{i, j}$。

• 接下来 $q$ 行，每行包含 $n$ 个整数；其中第 $k$ 行的第 $i$ 个整数为 $c_{k, i}$。

对于输入的每一行，如果有多个数输入，则相邻两个数用恰好一个空格隔开。

输出格式

输出 $q$ 行，每行 1 个整数：第 $k$ 行的整数表示第 $k$ 个学生的 $A^2+D^2$ 的最大值。

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

提示

样例解释

有 2 个知识点，每个知识点有 4 道练习题；有 4 个学生。

以第 2 个学生为例，我们需要为该学生在第 1 个知识点中选择恰好 2 道练习题，在第 2 个知识点中选择恰好 1 道练习题。一种最优的方案是，在第 1 个知识点中选择第 1 道题和第 3 道题，在第 2 个知识点中选择第 1 道题。这些题目对于算法能力的提高为 $A=a_{1,1}+a_{1,3}+a_{2,1}=1+(-1)+0=0$，对于数据结构能力的提高为 $D=d_{1,1}+d_{1,3}+d_{2,1}=1+1+10=12$，此时 $A^2+D^2=144$，并且不存在更优的方案。

数据范围

$1 \leq n \leq 6$，$1 \leq m \leq 666$，$1 \leq q \leq 666$，所有的 $a_{i, j}$ 与 $d_{i, j}$ 均在 $[-10^9,10^9]$ 范围内。 对于最终测试数据，所有的 $c_{k, i}$ 均在 $[0, m]$ 范围内独立、均匀随机生成。

提示

输出的每个数可能非常大，甚至可能超过64位整数的范围。

• C++语言可以使用__int128_t类型表示带符号128位整数，或使用__uint128_t类型表示无符号128位整数；这两种数据类型无法直接进行输入/输出。

• Java语言可以使用BigInteger类。

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。