Bạn có một lưới ô vuông gồm \(R\) hàng và \(C\) cột. Các hàng được đánh số từ \(1\) đến \(R\), các cột được đánh số từ \(1\) đến \(C\). Trên ô nằm ở hàng i và cột \(j\) có \(G[i][j]\) miếng vàng, \(S[i][j]\) miếng bạc và \(B[i][j]\) miếng đồng.

Bạn cần đi từ ô góc trái trên (thuộc hàng \(1\) cột \(1\)) tới ô góc phải dưới (thuộc hàng \(R\) cột \(C\)) của lưới. Đường đi của bạn cần thoả mãn các điều kiện sau:

• Trong mỗi bước, bạn chỉ được đi từ vị trí hiện tại sang một trong bốn ô kề cạnh.
• Tổng số miếng đồng trên các ô bạn đã đi qua không quá \(K\).
• Đường đi của bạn cần có số bước nhỏ nhất có thể.
• Trong số các đường đi có số bước tối thiểu, bạn cần chọn đường đi sao cho (tổng số miếng vàng chia cho tổng số miếng bạc) xét trên các ô đã đi qua là lớn nhất

Input

Dòng đầu tiên chứa 3 số nguyên \(R, C, K\) \((1 \leq R*C \leq 160, 1 \leq K \leq 10^9)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(G[i][1] ... G[i][C]\) \((1 \leq G[i][j] \leq 10^6, G[1][1] = G[R][C] = 0)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(S[i][1] ... S[i][C]\) \((1 \leq S[i][j] \leq 10^6, S[1][1] = S[R][C] = 0)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(B[i][1] ... B[i][C]\) \((1 \leq B[i][j] \leq 10^6, B[1][1] = B[R][C] = 0)\)

Output:

• Gồm 1 dòng, in ra \(-1\) nếu không thể đi từ ô \((1,1)\) đến ô \((R,C)\), ngược lại in ra tỉ lệ vàng chia bạc lớn nhất. Đáp án của bạn được chấp nhận nếu sai khác không quá \(10^{-6}\) so với đáp án của ban giám khảo. Nói cách khác, gọi \(P\) là đáp số của bạn và \(J\) là đáp số của ban giám khảo, bạn sẽ được tính là giải đúng khi và chỉ khi \(\dfrac{|P - J|}{max(1, |J|)} \leq 10^{-6}\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (17 điểm): \(R*C \leq 50\)
• Subtask 2 (17 điểm): \(K \leq 3000\)
• Subtask 3 (29 điểm): \(G, S \leq 7\)
• Subtask 4 (37 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(100\) điểm.

Example