Nước LQ có $n$ thành phố, đánh số từ $0$ đến $n-1$ . Giữa hai thành phố bất kỳ trong $n$ thành phố này đều có đúng một con đường hai chiều, mọi cặp thành phố đều có thể đi thẳng tới nhau. Mỗi con đường có một độ bụi $D$ ; khi di chuyển giữa các thành phố, người ta luôn ưu tiên chọn tuyến đường có tổng độ bụi nhỏ nhất.

Định nghĩa chỉ số cốt lõi

Dùng chỉ số $P$ để đánh giá môi trường đi lại, công thức tính:

$P= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} d(i,j)$

trong đó $d(i,j)$ biểu thị độ bụi của tuyến đường có độ bụi nhỏ nhất từ thành phố $i$ đến thành phố $j$ .

Quy tắc cải tạo đường

1. Khi một thành phố tiến hành cải tạo đường, độ bụi của tất cả các con đường nối trực tiếp với thành phố đó sẽ giảm $1$ ;

2. Mỗi con đường có cận dưới độ bụi $L$ , khi đạt cận dưới thì không thể giảm thêm;

3. Chu kỳ cải tạo: ngày thứ $1$ thành phố số $0$ cải tạo → ngày thứ $2$ thành phố số $1$ cải tạo → … → ngày thứ $n$ thành phố số $n-1$ cải tạo → ngày thứ $n+1$ quay lại thành phố số $0$ và lặp lại theo chu kỳ.

Yêu cầu của bài toán

Tìm số ngày ít nhất cần trải qua để $P \le Q$ ;

• Nếu trạng thái ban đầu đã thỏa mãn, in ra $0$ ;

• Nếu không bao giờ thỏa mãn được, in ra $-1$ .

Dữ liệu vào

1. Dòng đầu tiên: hai số nguyên $n, Q$ , lần lượt biểu thị số thành phố và ngưỡng trên của chỉ số mục tiêu;

2. Tiếp theo là $n$ dòng: mỗi dòng gồm $n$ số nguyên, là ma trận độ bụi ban đầu $D$ ( $D_{ij}=D_{ji}, D_{ii}=0$ );

3. Tiếp theo là $n$ dòng: mỗi dòng gồm $n$ số nguyên, là ma trận cận dưới độ bụi $L$ ( $L_{ij}=L_{ji}, L_{ii}=0$ ).

Dữ liệu ra

In ra một số nguyên, là số ngày ít nhất thỏa mãn điều kiện.

Ví dụ

Input

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

Output

2

Ghi chú

Quy mô dữ liệu và ràng buộc

• 30% số test: $1 \le n \le 10$ , $0 \le L_{ij} \le D_{ij} \le 10$ ;

• 60% số test: $1 \le n \le 50$ , $0 \le L_{ij} \le D_{ij} \le 100000$ ;

• Tất cả các test: $1 \le n \le 100$ , $0 \le L_{ij} \le D_{ij} \le 100000$ , $0 \le Q \le 2^{31}-1$ .