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

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

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

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

具體的計劃是這樣的：

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

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

…

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

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

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

…

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

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

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

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

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

2

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

此時每對頂點(diǎn)之間的灰塵度最小的路線對應(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.

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

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

注意到邊 (0, 2) 的值減小了 1 ，但 (0, 1) 并沒有減小，因為 L_0,1 = 2 ，所以 (0, 1) 的值不可以再減小了。此時每對頂點(diǎn)之間的灰塵度最小的路線對應(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.

此時 P 仍為 12 。

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

此時每對頂點(diǎn)之間的灰塵度最小的路線對應(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.

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

所以答案是 2。

對于 30% 的評測用例，1 ≤ n ≤ 10 ，0 ≤ L_ij ≤ D_ij ≤ 10；

對于 60% 的評測用例，1 ≤ n ≤ 50 ，0 ≤ L_ij ≤ D_ij ≤ 100000；

對于所有評測用例，1 ≤ n ≤ 100 ，0 ≤ L_ij ≤ D_ij ≤ 100000 ，0 ≤ Q ≤ 2³¹ ? 1。