题目描述

AtCoder World Tour Finals 2800 有 $N$ 名选手参加，比赛共设置了 $5$ 道题目。每道题目的分值都是不小于 $1$ 的整数，并且题目的编号 $1$ 到 $5$ 满足分值广义单调递增（即后面的题目分值不小于前面的题目）。这里不设部分分。

此外，排名规则与通常的 AtCoder 规则相同，具体如下（本题中不会出现总分和罚时都相同的情况）：

• 排名规则：总分高的选手排名更高；如果总分相同，则罚时更少的选手排名更高。

现在，负责 AtCoder World Tour Finals 采访的青木记者记录下了以下信息：

1. 参赛人数 $N$。
2. 每位选手解答每道题目的情况。若 $A_{i,j}=1$，表示第 $i$ 位选手（$1\leq i\leq N$）解出了第 $j$ 题，否则 $A_{i,j}=0$。
3. 每位选手的排名。第 $i$ 位选手（$1\leq i\leq N$）获得了 $R_i$ 名。

但在准备写稿时，他发现自己没有记录分值和罚时的信息，并且也意识到自己记录的信息可能存在矛盾。请你解决以下问题：

假设记录 1 和记录 2 是正确的。记第 $i$ 位选手的实际排名为 $D_i$，请你求出二乘误差之和 $(D_1-R_1)^2 + (D_2-R_2)^2 + \dots + (D_N-R_N)^2$ 的最小可能值。

给定 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入格式

输入按以下格式从标准输入读入。这里 $\mathrm{case}_i$ 表示第 $i$ 个（$1\leq i\leq T$）测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的输入格式如下：

$N$
$A_{1,1}$ $A_{1,2}$ $A_{1,3}$ $A_{1,4}$ $A_{1,5}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$ $A_{2,4}$ $A_{2,5}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $A_{N,3}$ $A_{N,4}$ $A_{N,5}$
$R_1$ $R_2$ $\cdots$ $R_N$

输出格式

请输出答案。

样例 1

输入

6
4
0 1 1 0 0
1 0 0 1 0
1 1 0 1 0
1 0 1 0 0
1 2 3 4
8
0 1 0 0 0
1 1 0 1 0
0 1 1 0 1
1 0 0 0 0
1 1 0 1 0
0 1 0 0 0
0 0 0 1 0
0 1 1 1 1
7 4 2 8 3 6 5 1
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
1 2 3 4 5 6
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
6 5 4 3 2 1
20
0 0 0 0 1
0 0 1 0 0
1 1 0 0 1
1 0 1 0 1
0 0 0 1 1
0 0 1 1 1
1 1 1 1 0
1 1 0 1 0
0 0 1 1 0
1 0 1 0 0
0 1 0 0 1
0 1 1 1 1
1 1 1 1 1
0 1 0 1 0
1 0 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 0 1 0
1 1 1 0 1
1 1 0 1 1
7 18 3 5 19 11 13 2 4 10 14 15 17 6 16 9 8 12 1 20
15
0 0 1 1 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
1 1 0 0 1
0 1 1 1 0
1 1 1 1 1
0 1 1 0 1
1 1 0 1 0
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
0 1 0 1 0
1 1 0 0 0
0 1 0 0 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

输出

6
0
26
0
1054
428

说明/提示

限制条件

• $1\leq T\leq 10^5$
• $2\leq N\leq 3\times 10^5$
• $A_{i,1},A_{i,2},A_{i,3},A_{i,4},A_{i,5}$ 为 $0$ 或 $1$（$1\leq i\leq N$）
• $A_{i,1}+A_{i,2}+A_{i,3}+A_{i,4}+A_{i,5}\geq 1$（$1\leq i\leq N$）
• $1\leq R_i\leq N$（$1\leq i\leq N$）
• $R_1,R_2,\dots,R_N$ 互不相同
• 所有测试用例中 $N$ 的总和不超过 $3\times 10^5$
• 所有输入均为整数

样例解释 1

本输入共包含 $6$ 个测试用例，先说明第 $1$ 个测试用例。

假设如下情况：

• 第 $1,2,3,4,5$ 题的分值分别为 $100$、$500$、$800$、$900$、$1300$。
• 第 $1,2,3,4$ 位参赛者的罚时分别为 $90$ 分、$80$ 分、$70$ 分、$60$ 分。

此时，排名表如下，二乘误差之和为 $(2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6$。不存在使二乘误差之和小于 $5$ 的方法，因此答案为 $6$。

参赛者	问 1	问 2	问 3	问 4	问 5	总分	罚时	排名
1	-	500	800	-		1300	90	2
2	100	-		900	1000	80	3
3	500	1500	70	1
4	-	800	-	900	60	4

接下来说明第 $2$ 个测试用例。

假设如下情况：

• 第 $1,2,3,4,5$ 题的分值分别为 $1000$、$1400$、$2000$、$2000$、$2718$。
• 第 $1,2,\dots,8$ 位参赛者的罚时分别为 $295$ 分、$286$ 分、$242$ 分、$236$ 分、$277$ 分、$288$ 分、$187$ 分、$299$ 分。

此时，排名表如下。对于任意 $i$（$1\leq i\leq N$），第 $i$ 位参赛者的排名均为 $R_i$，因此二乘误差之和为 $0$。

参赛者	问 1	问 2	问 3	问 4	问 5	总分	罚时	排名
1	-	1400	-			1400	295	7
2	1000	2000	4400	286	4
3	-		-	2718	6118	242	2
4	1000	-		-	1000	236	8
5	1400	2000	4400	277	3
6	-	-	1400	288	6
7		2000	2000	187	5
8	1400		2718	8118	299	1

由 ChatGPT 4.1 翻译