問題文

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

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

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

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

人$1 \rarr$ 人$2 \rarr$ $... \rarr$ 人$X \rarr$ 人$X\rarr$ $...\rarr$ 人$1$

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

問題は全部で $2X$ 問あり、$i$ 問目を解くのに人 $j$ は $A_{i,j}$ 秒かかります。

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

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

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

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

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

制約

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

入力

出力

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

サンプル

2 20
1 5
3 2
2 6
4 3

8

問題を $1\rarr$ $2 \rarr$ $4\rarr$ $3$ の順に解くのが最適です。

2 10
2 4
3 6
1 2
4 -1

-1

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

1 5
2
3

5

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

かわいそうですね。