(2024/10/9 22:48 追記) コンテストの際に問題文に誤りがありましたが、現在は問題文が修正されています。

あなたは $(1, 2, ..., N)$ を並び替えた順列 $P = (P_1, P_2, ..., P_N)$ を持っています。

また、$i$ 日目 ($1 \leq i \leq T$) に対して流行りの順列 $Q_i = (Q_{i,1}, Q_{i,2}, ..., Q_{i,N})$ が定められており、その日の幸福度は $P_j = Q_{i,j}$ となる整数 $j$ ($1 \leq j \leq N$) の個数です。

(例：あなたの持つ順列が $P = (1, 3, 2, 4)$ で $Q_i = (4, 3, 1, 2)$ のとき、2 番目の要素のみが等しいため、幸福度は $1$ である。)

更に、あなたは気合ポイントを消費することで、毎日その日が始まる瞬間にあなたの持っている順列を並び替えることができます。

このとき消費する気合ポイントは、元の順列を $R = (R_1, R_2, ..., R_N)$ 、 変更後の順列を $R' = (R'_1, R'_2, ..., R'_N)$ としたとき、

（順序付きの）組 $(i, j) (1 \leq i, j \leq N)$ であって、$\mathrm{pos}(R,\space i) < \mathrm{pos}(R,\space j) $ かつ $\mathrm{pos}(R',\space i) > \mathrm{pos}(R',\space j)$

となる組の数に等しくなります。

ただし、長さ $N$ の順列 $P = (P_1, P_2, ..., P_N)$ に対し、$\mathrm{pos}(P, j)$ を $\underline{P_i = j を満たす添字 i}$ と定義します。

$T$ 日間に渡る（幸福度の合計） - （消費した気合ポイントの合計）を最大化してください。

• 入力は全て整数
• $ 1 \leq N \leq 8 $
• $ 1 \leq T \leq 5 $
• $P$、$Q_i$ は $(1, 2, ..., N)$ を並び替えた順列
• $P$、$Q_i$ は 空白区切りで与えられる。入出力例も参照のこと

入力は以下の形式で標準入力から与えられます。

答えを1行に出力してください。