Mụ phù thủy có một khu hầm hình chữ nhật gồm \(N\) x \(M\) căn hầm. Các căn hầm được đánh số từ dòng từ \(1\) đến \(N\) theo chiều từ trên xuống dưới, đánh số cột từ \(1\) đến \(M\) theo chiều từ trái qua phải. Giữa hai căn hầm sát nhau có cửa thông nhau mà phải mất một khoảng thời gian nào đó mới có thể mở cửa để đi từ căn hầm này sang căn hầm kia. Sau khi bắt cóc công chúa, mụ phù thủy giam nàng tại căn hầm cuối cùng \([N,M]\) - dòng \(N\) cột \(M\) . Chàng thợ sửa ống nước Super Mario đang ở căn hầm đầu tiên \([1, 1]\). Bạn hãy tìm các căn hầm mà Mario phải đi qua để giải cứu công chúa sao cho thời gian là ngắn nhất.

Đầu vào

Dòng thứ nhất là hai số nguyên n và m cách nhau một khoảng trắng \((1 ≤ n, m ≤ 700)\)

N dòng tiếp theo, mỗi dòng gồm M-1 số nguyên \(a[i][j]\) là khoảng thời gian để mở cửa từ căn hầm \([i, j]\) sang căn hầm \([i, j+1]\) \((1 ≤ a[i][j] ≤ 10^5)\)

N-1 dòng tiếp theo, mỗi dòng gồm M số nguyên \(b[i][j]\) là khoảng thời gian để mở cửa từ căn hầm \([i, j]\) sang căn hầm \([i +1, j]\) \((1 ≤ b[i][j] ≤ 10^5)\)

Đầu ra

Một dòng duy nhất là thời gian ngắn nhất để mario giải cứu được công chúa

Ví dụ

Input

3 4
1 1 1
1 1 1
1 1 1
9 9 9 1
1 9 9 9

Output

11

Giải thích

Hướng đi của Mario như sau:

=>Thời gian ngắn nhất là: 1+1+1+1+1+1+1+1+1+1+1=11