LQ 國(guó)擁有 n 個(gè)城市，從 0 到 n ? 1 編號(hào)，這 n 個(gè)城市兩兩之間都有且僅有一條雙向道路連接，這意味著任意兩個(gè)城市之間都是可達(dá)的。每條道路都有一個(gè)屬性 D ，表示這條道路的灰塵度。當(dāng)從一個(gè)城市 A 前往另一個(gè)城市 B 時(shí)，可能存在多條路線，每條路線的灰塵度定義為這條路線所經(jīng)過的所有道路的灰塵度之和，LQ 國(guó)的人都很討厭灰塵，所以他們總會(huì)優(yōu)先選擇灰塵度最小的路線。

LQ 國(guó)很看重居民的出行環(huán)境，他們用一個(gè)指標(biāo) P 來衡量 LQ 國(guó)的出行環(huán)境，P 定義為：

其中 d(i, j) 表示城市 i 到城市 j 之間灰塵度最小的路線對(duì)應(yīng)的灰塵度的值。

為了改善出行環(huán)境，每個(gè)城市都要有所作為，當(dāng)某個(gè)城市進(jìn)行道路改善時(shí)，會(huì)將與這個(gè)城市直接相連的所有道路的灰塵度都減少 1，但每條道路都有一個(gè)灰塵度的下限值 L，當(dāng)灰塵度達(dá)到道路的下限值時(shí)，無論再怎么改善，道路的灰塵度也不會(huì)再減小了。

具體的計(jì)劃是這樣的：

第 1 天，0 號(hào)城市對(duì)與其直接相連的道路環(huán)境進(jìn)行改善；

第 2 天，1 號(hào)城市對(duì)與其直接相連的道路環(huán)境進(jìn)行改善；

…

第 n 天，n ? 1 號(hào)城市對(duì)與其直接相連的道路環(huán)境進(jìn)行改善；

第 n + 1 天，0 號(hào)城市對(duì)與其直接相連的道路環(huán)境進(jìn)行改善；

第 n + 2 天，1 號(hào)城市對(duì)與其直接相連的道路環(huán)境進(jìn)行改善；

…

LQ 國(guó)想要使得 P 指標(biāo)滿足 P ≤ Q。請(qǐng)問最少要經(jīng)過多少天之后，P 指標(biāo)可以滿足 P ≤ Q。如果在初始時(shí)就已經(jīng)滿足條件，則輸出 0 ；如果永遠(yuǎn)不可能滿足，則輸出 ?1。 

輸入的第一行包含兩個(gè)整數(shù) n, Q，用一個(gè)空格分隔，分別表示城市個(gè)數(shù)和期望達(dá)到的 P 指標(biāo)。

接下來 n 行，每行包含 n 個(gè)整數(shù)，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，其中第 i 行第 j 列的值 D_ij (D_ij = D_ji, D_ii = 0) 表示城市 i 與城市 j 之間直接相連的那條道路的灰塵度。

接下來 n 行，每行包含 n 個(gè)整數(shù)，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，其中第 i 行第 j 列的值 L_ij (L_ij = L_ji, L_ii = 0) 表示城市 i 與城市 j 之間直接相連的那條道路的灰塵度的下限值。

輸出一行包含一個(gè)整數(shù)表示答案。

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

2

初始時(shí)的圖如下所示，每條邊上的數(shù)字表示這條道路的灰塵度：

此時(shí)每對(duì)頂點(diǎn)之間的灰塵度最小的路線對(duì)應(yīng)的灰塵度為：

d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3,

d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1,

d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0.

初始時(shí)的 P 指標(biāo)為 (2 + 3 + 1) × 2 = 12，不滿足 P ≤ Q = 10;

第一天，0 號(hào)城市進(jìn)行道路改善，改善后的圖示如下：

注意到邊 (0, 2) 的值減小了 1 ，但 (0, 1) 并沒有減小，因?yàn)?L_0,1 = 2 ，所以 (0, 1) 的值不可以再減小了。此時(shí)每對(duì)頂點(diǎn)之間的灰塵度最小的路線對(duì)應(yīng)的灰塵度為：

d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3,

d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1,

d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0.

此時(shí) P 仍為 12 。

第二天，1 號(hào)城市進(jìn)行道路改善，改善后的圖示如下：

此時(shí)每對(duì)頂點(diǎn)之間的灰塵度最小的路線對(duì)應(yīng)的灰塵度為：

d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2,

d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0,

d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0.

此時(shí)的 P 指標(biāo)為 (2 + 2) × 2 = 8 < Q ，此時(shí)已經(jīng)滿足條件。

所以答案是 2。

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ n ≤ 10 ，0 ≤ L_ij ≤ D_ij ≤ 10；

對(duì)于 60% 的評(píng)測(cè)用例，1 ≤ n ≤ 50 ，0 ≤ L_ij ≤ D_ij ≤ 100000；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 100 ，0 ≤ L_ij ≤ D_ij ≤ 100000 ，0 ≤ Q ≤ 2³¹ ? 1。