Mụ phù thủy có một khu hầm hình chữ nhật gồm ~n \times 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]~. Chàng thợ sửa ống nước Super Mario đang ở căn hầm đầu tiên ~[1, 1]~. Hãy tìm các căn hầm mà Mario phải đi qua để giải cứu công chúa một cách nhanh nhất.

Yêu cầu: Xác định khoảng thời gian sớm nhất mà Mario giải cứu công chúa.

Input

• Dòng thứ nhất là hai số nguyên ~n~ và ~m~ cách nhau một khoảng trắng (~1 \le n, m \le 700~).
• Trong ~n~ dòng tiếp theo mỗi dòng gồm ~m-1~ số nguyên ~a_{ij}~ 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 \le a_{ij} \le 10^5~).
• Trong ~n-1~ dòng tiếp theo mỗi dòng gồm ~m~ số nguyên ~b_{ij}~ 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 \le b_{ij} \le 10^5~).

Output

• Là số nguyên xác định khoảng thời gian sớm nhất mà Mario giải cứu công chúa.

Sample Input 1

3 4
1 1 1
1 1 1
1 1 1
10 0
20 1
5 1

Sample Output 1

11