問題文

今年もクリスマスの時期がやってきました！

サンタさんであるあなたは，一年間良い子にしていた子供たちにプレゼントを渡そうと思っています。
子供は $N$ 人おり，おもちゃは全部で $M$ 種類あります。
$i \;(1≤i≤N)$ 人目の子供は，欲しいおもちゃ $A_i , B_i , C_i , D_i , E_i$ をサンタさんに頼みました。

また，どのおもちゃを貰ったかによって，子供が感じる「嬉しさ」には違いがあります。
具体的には，$A_i$ を貰うと $p_i$ , $B_i$ を貰うと $q_i$ , $C_i$ を貰うと $r_i$ , $D_i$ を貰うと $s_i$ , $E_i$ を貰うと $t_i$ の「嬉しさ」を感じます。

あなたは経済的な問題により，全員にそのうちどれか $1$ つのおもちゃを選んでプレゼントすることにしました。

また，サンタ業界は色々なおもちゃメーカーと繋がりを持っていて，在庫と関係維持のために，全部で $M$ 種類あるおもちゃにおいて，$j\;(1≤j≤M)$ 種類目のおもちゃについて，配らなければならない最低限の個数 $F_j$ と配ることのできる最大個数 $G_j$ が決められています。

つまり，あなたは，$j$ 種類目のおもちゃを $x_j$ 個配るとしたとき，$x_j$ は $F_j≤x_j≤G_j$ を満たさなければなりません。

この条件を満たし，かつ子ども全員の希望を満たすおもちゃの選び方が存在するか判定し，存在するならば，その中で最適なおもちゃの選び方をした時，子供たちが感じる「嬉しさ」の合計の最大値を求めてください。

制約

$5≤N≤10^3$
$5≤M≤10^2$
$1≤A_i,B_i,C_i,D_i,E_i≤M$
$1≤p_i,q_i,r_i,s_i,t_i≤10^9$
$1≤F_i,G_i≤N$

入力

出力

子供たちが感じる「嬉しさ」の合計の最大値を一行に出力してください。
また，条件を満たすおもちゃの選び方が存在しない場合，-1 を出力してください。

入力例 $1$

5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1
1 1
1 1
1 1
1 1

出力例 $1$

5

子供 $1,2,3,4,5$ にそれぞれおもちゃ $1,2,3,4,5$ を配れば良いです。

入力例 $2$

5 5
1 3 4 5 2
3 2 5 4 1
1 5 2 4 3
5 2 3 1 4
5 1 3 4 2
3 9 6 3 5
5 2 10 4 7
10 4 2 10 2
6 2 6 5 4
10 4 5 8 4
1 1
1 1
1 1
1 1
1 1

出力例 $2$

39

子供 $1,2,3,4,5$ にそれぞれおもちゃ $3,5,1,2,4$ をあげれば良いです。

入力例 $3$

7 5
1 4 5 2 3
3 4 2 1 5
4 1 3 5 2
4 2 3 1 5
3 2 1 4 5
3 4 2 5 1
3 1 2 4 5
5 8 2 8 4
7 1 9 8 7
6 8 6 7 9
1 3 2 2 7
9 1 3 4 5
7 8 4 3 3
8 1 9 8 1
2 2
2 2
1 2
1 1
1 2

出力例 $3$

57

入力例 $4$

6 6
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
3 1 4 2 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1
1 1
1 1
1 1
1 1
1 1

出力例 $4$

-1

子ども $1,2,3,4,5,6$ に $1,2,3,4,5,6$ を配れば$F,G$ の最低限の個数，最大個数の条件は達成できますが，子ども $6$ に希望するおもちゃをあげられません。
子ども全員に希望するおもちゃをあげることができないので，出力すべき値は -1 となります。

入力例 $5$

5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
20000000 1 1 1 1
1 210000 1 1 1
1 1 1200 1 1
1 1 1 20 1
1 1 1 1 5
1 1
1 1
1 1
1 1
1 1

出力例 $5$

20211225

謝辞

この問題を作るにあたって，bayashikoさんに多大なご協力を頂きました。ありがとうございました。