~XXX~ là một nhà khai phá tài ba. Vào một ngày đẹp trời, ~XXX~ phát hiện một quần đảo gồm ~n~ hòn đảo nhỏ, được đánh số từ ~1~ đến ~n~. Bỗng nhiên, tại trung tâm của những hòn đảo lung linh xinh đẹp ấy, một vị thần đèn khổng lồ từ từ trồi lên khỏi mặt nước. Ngài tự xưng mình là ~YYY~, vị thần đèn vĩ đại nhất thế giới, sẽ ban cho ~XXX~ một thử thách khó nhằn cùng với phần thưởng vô cùng to lớn.

Thần đèn ~YYY~ ban đầu ban cho ~XXX~ một lượng lớn vàng ~D~ và bắt đầu thử thách sử dụng số vàng ấy. Sau khi hoàn thành xong thử thách, ~XXX~ có thể giữ lại lượng vàng còn lại.

Thử thách của ~YYY~ yêu cầu ~XXX~ xây dựng những cây cầu bằng vàng giữa những hòn đảo, giữa hòn đảo thứ ~i~ và thứ ~j~ nếu xây dựng cây cầu sẽ tốn ~c_{i, j}~ đơn vị vàng. Ngoài ra sau khi xây xong, quần đảo phải có những thuộc tính sau:

• Giữa ~2~ hòn đảo không có quá ~1~ cây cầu.

• Mỗi hòn đảo chỉ được kết nối với đúng 2 hoặc 0 hòn đảo khác thông qua những cây cầu vàng.

• Có ít nhất một hòn đảo được kết nối với đúng 2 hòn đảo khác thông qua những cây cầu vàng.

Hãy cho biết ~XXX~ có thể vượt qua thử thách của thần đèn hay không nhé! Nếu ~XXX~ có thể vượt qua thử thách của thần đèn, hãy cho biết số vàng lớn nhất mà ~XXX~ có thể nhận được là bao nhiêu.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n~) và ~D~ (~0 \le D \le 10^{18}~) cho biết số lượng hòn đảo trong quần đảo và số lượng đơn vị vàng ban đầu được ban tặng.

Trong ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên dương, số ở dòng thứ ~i~ và cột thứ ~j~ gọi là ~c_{i, j}~ (~0 < c_{i, j} \le 10^9~) cho biết lượng vàng phải bỏ ra khi xây dựng cầu giữa hòn đảo thứ ~i~ và hòn đảo thứ ~j~. Riêng với ~c_{i, i} = 0,\,\forall i = \overline{1..n}~.

Output

Nếu có thể thành công hoàn thành thử thách, in ra một dòng duy nhất một số nguyên là số lượng vàng lớn nhất có thể đạt được sau khi hoàn thành thử thách.

Nếu không thể hoàn thành thử thách, in ra "~-1~" (không bao gồm dấu ngoặc kép).

Scoring

Sample Input 1

3 10
0 1 1
1 0 1
1 1 0

Sample Output 1

7

Sample Input 2

3 0
0 1 1
1 0 1
1 1 0

Sample Output 2

-1