問題文

Syntax君は制限時間内に XX 人で一人 22 問ずつ問題を解ききるゲームに参加しています。同じ問題を重複して答えることはできません。

全ての問題を解くことができた場合、クリアです。

TT 秒までにクリアできなかった場合、爆弾が爆発し、ゲームオーバーです。

某番組と同じ順に進行、すなわち

11 \rarr22 \rarr ...... \rarrXX \rarrXX\rarr ......\rarr11

の順番に問題を解きます。

問題は全部で 2X2X 問あり、ii 問目を解くのに人 jjAi,jA_{i,j} 秒かかります。

ただし、解くことができない場合は Ai,j=1A_{i,j}=-1 です。

1111 問目を解き始めた時間を 00 秒とし、ある人が解くのに ss 秒かかる問題を tt 秒目に解き始めた場合 t+st+s 秒になる直前に解き終わるものとします。

また、人 112X2X 問目を解き終わるのが uu(uT)(u\leq T) になる直前であった時、クリア時間は uu 秒です。

112X2X 問目を解き終わる時間を uu 秒として u>Tu > T である時やそもそも全ての問題を解くことができない場合は爆発します。

爆発させずに全ての問題を解くことができるかを判定し、クリアできる場合は最小のクリア時間を出力してください。

制約

  • 入力はすべて整数
  • 1X81 \leq X \leq 8
  • 1T1091 \leq T \leq 10^9
  • Ai,j=1A_{i,j}=-1 または 1Ai,j1091 \leq A_{i,j} \leq 10^9

入力

XTX \hspace{0.5em} T\\ A1,1A1,2A1,XA_{1,1}\hspace{0.5em} A_{1,2}\hspace{0.5em} {\ldots}\hspace{0.5em} A_{1,X}\\ A2,1A2,2A2,XA_{2,1}\hspace{0.5em} A_{2,2} \hspace{0.5em}{\ldots}\hspace{0.5em} A_{2,X}\\ \vdots\\ A2X,1A2X,2A2X,XA_{2X,1}\hspace{0.5em} A_{2X,2} \hspace{0.5em}{\ldots}\hspace{0.5em} A_{2X,X}\\

出力

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

サンプル

入力例1
2 20
1 5
3 2
2 6
4 3
出力例1
8

問題を 11\rarr 22 \rarr 44\rarr 33 の順に解くのが最適です。


入力例2
2 10
2 4
3 6
1 2
4 -1
出力例2
-1

どの順番で解いても時間切れとなり、爆発してしまいます。


入力例3
1 5
2
3
出力例3
5

Syntax君は 11 人ぼっちですが、ゲームに参加しなくてはなりません。

かわいそうですね。

Submit


Go (1.21)