Score: $1000$ points

问题陈述

在AtCoder世界巡回赛决赛2800中，共有$N$名参赛者参加，共提出了五个问题。每个问题都分配了一个至少为1分的整数分数，并且问题编号是按照从问题1到问题5的非递减顺序排列的。没有部分分数。根据AtCoder的常规规则，排名如下。在这个问题中，我们不考虑多个参赛者具有相同总分和罚分的情况。

排名：总分更高的参赛者排名更高。如果出现平局，罚分较小的参赛者排名更高。

现在，负责报道决赛的记者青木注意到了以下信息：

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。设$D_i$为参赛者$i$（$1 \leq i \leq N$）的实际排名，并找到可能的最小总平方误差$(D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2$。

您有$T$个测试用例需要处理。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

In the AtCoder World Tour Finals 2800, $N$ contestants participated, and a total of five problems were presented. Each problem is assigned an integer score of at least $1$ point, and the problems are numbered so that the scores are non-decreasing from problem $1$ to problem $5$. There are no partial points. Similar to the usual AtCoder rules, ranking is done as follows. In this problem, we do not consider the situation where multiple contestants have the same total score and penalty.

RankingThe contestant with the higher total score ranks higher. In case of a tie, the one with the smaller penalty ranks higher.

Now, Aoki, a reporter covering the finals, noted the following information:

1. The number of participants $N$.
2. Which problems each contestant solved. $A_{i,j}=1$ means the $i$-th contestant $(1 \leq i \leq N)$ correctly solved problem $j$, and $A_{i,j}=0$ means they did not.
3. The rank of each contestant. The $i$-th contestant $(1 \leq i \leq N)$ was ranked $R_i$-th.

However, when he started writing the article, he realized he did not note the scores and penalties. Furthermore, he realized there might be inconsistencies in the information he noted. Now, solve the following problem.

Assume that he correctly noted information 1 and 2. Let $D_i$ be the actual rank of contestant $i$ $(1 \leq i \leq N)$, and find the minimum possible total squared error $(D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2$.

You have $T$ test cases to process.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 3 \times 10^5$
• Each of $A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5}$ is $0$ or $1$ $(1 \leq i \leq N)$.
• The sum of $A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5}$ is at least $1$ $(1 \leq i \leq N)$.
• $1 \leq R_i \leq N$ $(1 \leq i \leq N)$
• $R_1, R_2, \dots, R_N$ are distinct.
• The total value of $N$ across all test cases is at most $3 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here $\mathrm{case}_i$ represents the $i$-th test case $(1 \leq i \leq T)$.

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

Each test case is given in the following format:

$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$

Output

Print the answers.

Sample Input 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

Sample Output 1

6
0
26
0
1054
428

This input contains six test cases. Let us explain the first one.

Consider the following scenario.

• Problems $1$, $2$, $3$, $4$, $5$ have $100$, $500$, $800$, $900$, $1300$ points, respectively.
• Contestants $1$, $2$, $3$, $4$ have penalties of $90$, $80$, $70$, $60$ minutes, respectively.

Then, the ranking will be as shown in the table below, where the total squared error is $(2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6$. There is no way to make the total squared error $5$ or less, so the answer is $6$.

Contestant	Problem 1	Problem 2	Problem 3	Problem 4	Problem 5	Total score	Penalty	Rank
Contestant 1	-	500	800	-	-	1300	90 minutes	2nd
Contestant 2	100	-	-	900	-	1000	80 minutes	3rd
Contestant 3	100	500	-	900	-	1500	70 minutes	1st
Contestant 4	100	-	800	-	-	900	60 minutes	4th

---

Now, let us explain the second test case.

Consider the following scenario.

• Problems $1$, $2$, $3$, $4$, $5$ have $1000$, $1400$, $2000$, $2000$, $2718$ points, respectively.
• Contestants $1$, $2$, $\dots$, $8$ have penalties of $295$, $286$, $242$, $236$, $277$, $288$, $187$, $299$ minutes, respectively.

Then, the ranking will be as shown in the table below. For every $i$ $(1 \leq i \leq N)$, the rank of contestant $i$ is $R_i$, so the total squared error is $0$.

Contestant	Problem 1	Problem 2	Problem 3	Problem 4	Problem 5	Total score	Penalty	Rank
Contestant 1	-	1400	-	-	-	1400	295 minutes	7th
Contestant 2	1000	1400	-	2000	-	4400	286 minutes	4th
Contestant 3	-	1400	2000	-	2718	6118	242 minutes	2nd
Contestant 4	1000	-	-	-	-	1000	236 minutes	8th
Contestant 5	1000	1400	-	2000	-	4400	277 minutes	3rd
Contestant 6	-	1400	-	-	-	1400	288 minutes	6th
Contestant 7	-	-	-	2000	-	2000	187 minutes	5th
Contestant 8	-	1400	2000	2000	2718	8118	299 minutes	1st