AT_arc177_e [ARC177E] Wrong Scoreboard

[problemUrl]: https://atcoder.jp/contests/arc177/tasks/arc177_e AtCoder World Tour Finals 2800 には $ N $ 人の選手が参加し、全 $ 5 $ 問の問題が出題されました。 各問題には $ 1 $ 点以上の整数の配点が付けられており、配点が**広義単調増加**になるように、問 $ 1 $ から問 $ 5 $ までの問題番号が付けられています。 ここで部分点はありません。 また、通常の AtCoder のルールと同様、以下の方法で順位付けが行われます。**なお、本問では合計得点もペナルティも同じという状況は考えないことにします。** 順位付けの方法合計得点の高い方が上の順位となる。同点の場合は、ペナルティが $ 1 $ 秒でも少ない方が上の順位となる。さて、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 $ $ (1\ \leq\ i\ \leq\ N) $ の実際の順位を $ 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\ \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} $ の合計は $ 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 $ 以下 - 入力はすべて整数 ### Sample Explanation 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 番目\*\* 100 500 - 900 - 1500 70 分 1 位 \*\*4 番目\*\* 100 - 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 1400 - 2000 - 4400 286 分 4 位 \*\*3 番目\*\* - 1400 2000 - 2718 6118 242 分 2 位 \*\*4 番目\*\* 1000 - - - - 1000 236 分 8 位 \*\*5 番目\*\* 1000 1400 - 2000 - 4400 277 分 3 位 \*\*6 番目\*\* - 1400 - - - 1400 288 分 6 位 \*\*7 番目\*\* - - - 2000 - 2000 187 分 5 位 \*\*8 番目\*\* - 1400 2000 2000 2718 8118 299 分 1 位