{"raw_statement":[{"iden":"problem statement","content":"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.**\nRankingThe 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:\n\n1.  The number of participants $N$.\n2.  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.\n3.  The rank of each contestant. The $i$\\-th contestant $(1 \\leq i \\leq N)$ was ranked $R_i$\\-th.\n\nHowever, 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.\n\n> 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$.\n\nYou have $T$ test cases to process."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 3 \\times 10^5$\n*   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)$.\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)$.\n*   $1 \\leq R_i \\leq N$ $(1 \\leq i \\leq N)$\n*   $R_1, R_2, \\dots, R_N$ are distinct.\n*   The total value of $N$ across all test cases is at most $3 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"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)$.\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_{1,1}$ $A_{1,2}$ $A_{1,3}$ $A_{1,4}$ $A_{1,5}$\n$A_{2,1}$ $A_{2,2}$ $A_{2,3}$ $A_{2,4}$ $A_{2,5}$\n$\\vdots$\n$A_{N,1}$ $A_{N,2}$ $A_{N,3}$ $A_{N,4}$ $A_{N,5}$\n$R_1$ $R_2$ $\\cdots$ $R_N$"},{"iden":"sample input 1","content":"6\n4\n0 1 1 0 0\n1 0 0 1 0\n1 1 0 1 0\n1 0 1 0 0\n1 2 3 4\n8\n0 1 0 0 0\n1 1 0 1 0\n0 1 1 0 1\n1 0 0 0 0\n1 1 0 1 0\n0 1 0 0 0\n0 0 0 1 0\n0 1 1 1 1\n7 4 2 8 3 6 5 1\n6\n1 1 0 0 0\n0 0 1 0 0\n1 1 1 0 0\n0 0 0 1 0\n1 1 1 1 0\n0 0 0 0 1\n1 2 3 4 5 6\n6\n1 1 0 0 0\n0 0 1 0 0\n1 1 1 0 0\n0 0 0 1 0\n1 1 1 1 0\n0 0 0 0 1\n6 5 4 3 2 1\n20\n0 0 0 0 1\n0 0 1 0 0\n1 1 0 0 1\n1 0 1 0 1\n0 0 0 1 1\n0 0 1 1 1\n1 1 1 1 0\n1 1 0 1 0\n0 0 1 1 0\n1 0 1 0 0\n0 1 0 0 1\n0 1 1 1 1\n1 1 1 1 1\n0 1 0 1 0\n1 0 0 0 1\n1 1 1 0 0\n0 1 1 1 0\n0 0 0 1 0\n1 1 1 0 1\n1 1 0 1 1\n7 18 3 5 19 11 13 2 4 10 14 15 17 6 16 9 8 12 1 20\n15\n0 0 1 1 0\n0 0 0 1 0\n0 0 0 0 1\n0 0 1 1 1\n1 1 0 0 1\n0 1 1 1 0\n1 1 1 1 1\n0 1 1 0 1\n1 1 0 1 0\n1 0 0 1 1\n1 0 1 0 0\n1 1 0 1 1\n0 1 0 1 0\n1 1 0 0 0\n0 1 0 0 1\n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"},{"iden":"sample output 1","content":"6\n0\n26\n0\n1054\n428\n\nThis input contains six test cases. Let us explain the first one.\n\n> Consider the following scenario.\n> \n> *   Problems $1$, $2$, $3$, $4$, $5$ have $100$, $500$, $800$, $900$, $1300$ points, respectively.\n> *   Contestants $1$, $2$, $3$, $4$ have penalties of $90$, $80$, $70$, $60$ minutes, respectively.\n> \n> 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$.\n> \n> Contestant\n> \n> Problem 1\n> \n> Problem 2\n> \n> Problem 3\n> \n> Problem 4\n> \n> Problem 5\n> \n> Total score\n> \n> Penalty\n> \n> Rank\n> \n> **Contestant 1**\n> \n> \\-\n> \n> 500\n> \n> 800\n> \n> \\-\n> \n> \\-\n> \n> 1300\n> \n> 90 minutes\n> \n> 2nd\n> \n> **Contestant 2**\n> \n> 100\n> \n> \\-\n> \n> \\-\n> \n> 900\n> \n> \\-\n> \n> 1000\n> \n> 80 minutes\n> \n> 3rd\n> \n> **Contestant 3**\n> \n> 100\n> \n> 500\n> \n> \\-\n> \n> 900\n> \n> \\-\n> \n> 1500\n> \n> 70 minutes\n> \n> 1st\n> \n> **Contestant 4**\n> \n> 100\n> \n> \\-\n> \n> 800\n> \n> \\-\n> \n> \\-\n> \n> 900\n> \n> 60 minutes\n> \n> 4th\n\n* * *\n\nNow, let us explain the second test case.\n\n> Consider the following scenario.\n> \n> *   Problems $1$, $2$, $3$, $4$, $5$ have $1000$, $1400$, $2000$, $2000$, $2718$ points, respectively.\n> *   Contestants $1$, $2$, $\\dots$, $8$ have penalties of $295$, $286$, $242$, $236$, $277$, $288$, $187$, $299$ minutes, respectively.\n> \n> 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$.\n> \n> Contestant\n> \n> Problem 1\n> \n> Problem 2\n> \n> Problem 3\n> \n> Problem 4\n> \n> Problem 5\n> \n> Total score\n> \n> Penalty\n> \n> Rank\n> \n> **Contestant 1**\n> \n> \\-\n> \n> 1400\n> \n> \\-\n> \n> \\-\n> \n> \\-\n> \n> 1400\n> \n> 295 minutes\n> \n> 7th\n> \n> **Contestant 2**\n> \n> 1000\n> \n> 1400\n> \n> \\-\n> \n> 2000\n> \n> \\-\n> \n> 4400\n> \n> 286 minutes\n> \n> 4th\n> \n> **Contestant 3**\n> \n> \\-\n> \n> 1400\n> \n> 2000\n> \n> \\-\n> \n> 2718\n> \n> 6118\n> \n> 242 minutes\n> \n> 2nd\n> \n> **Contestant 4**\n> \n> 1000\n> \n> \\-\n> \n> \\-\n> \n> \\-\n> \n> \\-\n> \n> 1000\n> \n> 236 minutes\n> \n> 8th\n> \n> **Contestant 5**\n> \n> 1000\n> \n> 1400\n> \n> \\-\n> \n> 2000\n> \n> \\-\n> \n> 4400\n> \n> 277 minutes\n> \n> 3rd\n> \n> **Contestant 6**\n> \n> \\-\n> \n> 1400\n> \n> \\-\n> \n> \\-\n> \n> \\-\n> \n> 1400\n> \n> 288 minutes\n> \n> 6th\n> \n> **Contestant 7**\n> \n> \\-\n> \n> \\-\n> \n> \\-\n> \n> 2000\n> \n> \\-\n> \n> 2000\n> \n> 187 minutes\n> \n> 5th\n> \n> **Contestant 8**\n> \n> \\-\n> \n> 1400\n> \n> 2000\n> \n> 2000\n> \n> 2718\n> \n> 8118\n> \n> 299 minutes\n> \n> 1st"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}