Đặt bối cảnh Loli đang đi đu một concert, cái-mà-ai-cũng-biết ở Vinhomes Ocean Park 3. Thực ra thì concert diễn ra ở đâu Loli cũng đến và cổ vũ thôi, nhưng vì sức hút của chương trình quá đông, Loli lại không thể đặt được chỗ ngồi gần với các anh tài. Được cái, Loli chỉ thiếu vé chứ không thiếu tiền.

Chỗ ngồi ở sự kiện có dạng một lưới hình chữ nhật, với ~n~ hàng và ~m~ cột. Vị trí ở hàng ~i~ và cột ~j~ được kí hiệu ~(i,j)~. Loli dự định tiếp cận từ góc trên bên trái ~(1,1)~. Vị trí gần với các anh tài nhất nằm ở góc dưới bên phải ~(n,m)~.

Ngày diễn ra sự kiện, Loli có vẽ ra một kế hoạch thiên tài (nhắc lại, Loli chỉ vẽ thôi). Hắn sẽ lần lượt đổi chỗ của mình với người ngồi bên phải mình hoặc người bên dưới mình. Nói cách khác, nếu hắn đang ở ~(i,j)~, thì hắn có thể đổi với người ở vị trí ~(i+1,j)~ hoặc vị trí ~(i,j+1)~, miễn là vị trí đó hợp lệ.

Tất nhiên, cái gì cũng phải có cái giá của nó. Để được đổi tới vị trí mới, Loli sẽ phải trả toàn bộ phí "đổi chỗ" cho người ở vị trí mới. Nói cách khác, nếu vị trí cần tới là ~(i,j)~, thì phí cần trả là ~a_{i,j}~. Như vậy, trên đường đi vượt ngàn chông gai từ ~(1,1)~ tới ~(n,m)~, Loli sẽ phải trả tổng toàn bộ phí có trên đường đi đó (bao gồm phí ở ~(1,1)~ và ~(n,m)~).

Nhưng mà như thế thì dễ quá. Loli trong lúc hỏi giá đổi chỗ, thì có quen được một anh staff cao to đẹp trai. Anh này có đưa ra một lựa chọn rất hời nếu được sử dụng hợp lý: Với giá ~k~, anh sẽ dịch tất cả mọi người trên một hàng bất kỳ sang trái một ghế. Chi tiết hơn, nếu lựa chọn hàng ~i~, anh staff sẽ dịch người vị trí ~(i,m)~ sang ~(i,m-1)~, ~(i,m-1)~ sang ~(i,m-2)~, ..., ~(i,2)~ sang ~(i,1)~, người ở ~(i,1)~ được chuyển sang ~(i,m)~. Như vậy, phí "đổi chỗ" cũng được dịch theo tương ứng.

Loli có thể chọn dịch một hàng bất kỳ, và một hàng có thể được dịch nhiều lần, miễn là Loli trả đủ tiền cho anh staff. Tất nhiên, trước khi thực hiện phi vụ, Loli sẽ phải nói chi tiết kế hoạch dịch hàng cho anh staff. Nói cách khác, Loli không thể hú anh staff để dịch hàng khi đã ngồi xuống ghế.

Kết hợp hai thứ, các bạn có thể chỉ ra phương án cần ít vốn nhất cho Loli không?

Input

Đầu vào bao gồm nhiều test con.

Dòng đầu tiên chứa một số nguyên ~t\ (1\le t\le 10^3)~ – là số test con. Các test con có dạng sau đây:

• Dòng đầu tiên chứa hai số nguyên ~n, m\ (1\le n,m \le 360)~ – là số hàng và số cột của chỗ ngồi.

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên không âm ~a_{i,1}, a_{i,2}, \dots, a_{i,m}\ (0\le a_{i,j} \le 10^9)~ – là phí "đổi chỗ".

• Dòng cuối cùng chứa một số nguyên ~k\ (0\le k\le 10^9)~ – là phí dịch hàng sang trái một ghế.

Đầu vào đảm bảo tổng số lượng vị trí (người) trong toàn bộ các test con (tổng các ~n\times m~), đều không vượt quá ~130000~.

Output

Với mỗi test con, in ra trên một dòng một số nguyên là chi phí nhỏ nhất có thể.

Scoring

• Subtask 1: ~20\%~ số điểm có đáp án tối ưu không cần dịch hàng.

• Subtask 2: ~20\%~ số điểm có ~t = 1;\ n,m \le 3~;

• Subtask 3: ~40\%~ số điểm có ~t \le 10;\ n,m \le 100~;

• Subtask 4: ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

3
3 3
1 2 3
5 1 3
0 121 121
100
3 4
69 0 0 69
0 0 69 0
69 69 0 69
10
1 1
96
4

Sample Output 1

107
60
96

Notes

Ở test con thứ nhất, ta đạt được chi phí nhỏ nhất ~107~ bằng cách:

1. Dịch hàng 3 sang trái một lần. Lưới chỗ ngồi mới có phí: $$\begin{matrix}1 & 2 & 3\\5 & 1 & 3\\121 & 121 & 0\end{matrix}$$

2. Di chuyển như sau: ~(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3)~.

Như vậy, ta dịch hàng một lần trước khi đổi chỗ. Chi phí dịch hàng là ~k = 100~. Tổng chi phí đổi chỗ là ~1 + 2 + 1 + 3 + 0 = 7~. Tổng chi phí là ~100 + 7 = 107~.

Ở test con thứ hai, ta có thể dịch hàng 1 một lần, hàng 2 hai lần, hàng 3 ba lần. Lưới chỗ ngồi mới có phí: $$\begin{matrix}0 & 0 & 69 & 69 \\69 & 0 & 0 & 0\\69 & 69 & 69 & 0\end{matrix}$$

Tổng cộng ta dịch hàng ~6~ lần trước khi đổi chỗ. Chi phí dịch hàng là ~6\times k = 6\times 10 = 60~. Dễ thấy tồn tại cách di chuyển có chi phí ~0~. Như vậy, tổng chi phí là ~60 + 0 = 60~.