Cánh đồng nông sản chất lượng cao của một hợp tác xã nông nghiệp có dạng hình chữ nhật kích thước ~m \times n~ được chia thành ~m \times n~ ô vuông bởi các đường thẳng song song cạnh của hình chữ nhật. Các hàng của hình chữ nhật được đánh số ~1, 2, \dots, m~ từ trên xuống dưới và các cột của hình chữ nhật được đánh số ~1, 2, \dots, n~ từ trái sang phải. Ô vuông nằm ở giao của hàng ~i~ với cột ~j~ ký hiệu là ô ~(i, j)~, ~i = 1, 2, \dots, m~; ~j = 1, 2, \dots, n~.

Có hai công ty cấp nước sản xuất nông nghiệp. Công ty ~A~ đặt nguồn cung cấp ở bờ bên trái của cánh đồng, các đường ống do công ty này xây dựng sẽ chạy từ trái sang phải song song với cạnh của hình chữ nhật. Mức giá công ty ~A~ thông báo cho hợp tác xã để làm đường nước qua ô ~(i, j)~ là ~a_{ij}~. Công ty ~B~ đặt nguồn cung cấp ở bờ trên của hình chữ nhật, các đường ống do công ty này xây dựng chạy từ trên xuống dưới song song với cạnh của hình chữ nhật. Mức giá công ty ~B~ thông báo cho hợp tác xã để làm đường ống qua ô ~(i, j)~ là ~b_{ij}~. Mỗi ô của cánh đồng cần có đường nước đến ô này thuộc một trong hai công ty nói trên và ở một ô chỉ có đường ống của một công ty (các đường ống cấp nước của hai công ty không đi qua cùng một ô).

Hãy tìm cách xây dựng các đường ống cấp nước tưới sao cho tổng chi phí là nhỏ nhất?

Dữ liệu

• Dòng đầu tiên ghi hai số nguyên dương ~m, n~ (~m \times n \le 10^6~);
• ~m~ dòng tiếp theo, dòng thứ ~i~ ghi các số nguyên ~a_{i1}, a_{i2}, \dots, a_{in}~ (~0 \le a_{ij} \le 10^9~) cách nhau bởi dấu trống (~i = 1, 2, \dots, m~; ~j = 1, 2, \dots, n~);
• ~m~ dòng cuối cùng, dòng thứ ~i~ ghi các số nguyên ~b_{i1}, b_{i2}, \dots, b_{in}~ (~0 \le b_{ij} \le 10^9~) cách nhau bởi dấu trống (~i = 1, 2, \dots, m~; ~j = 1, 2, \dots, n~).

Kết quả

Ghi ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Ví dụ

WATER.INP

3 4
3 3 2 2
1 1 1 2
1 1 1 2
2 2 1 1
2 2 2 1
2 2 2 1

WATER.OUT

14

Minh họa:

Giới hạn

• Có 40% số test tương ứng với 40% số điểm của bài có ~m \times n \le 20~;
• Có 70% số test tương ứng với 70% số điểm của bài có ~m, n \le 300~;
• Có 100% số test tương ứng 100% số điểm của bài có ~m, n \le 10^6~.