Những năm gần đây, các cánh đồng vùng Đồng bằng sông Cửu Long phải đối mặt với nhiều thách thức do ảnh hưởng của biến đổi khí hậu, nước biển dâng, quá trình phát triển ở thượng nguồn sông Mê Công... gây tình trạng hạn hán, xâm nhập mặn, việc cung cấp nước là hết sức quan trọng. Với tình hình cấp bách đó có hai công ty cấp nước sản xuất nông nghiệp đã đứng ra nhận cung cấp cho cánh đồng vùng Đồng bằng sông Cửu Long. Cánh đồng có dạng hình chữ nhật kích thước \(m×n\) được chia thành \(m×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, ..., 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, ..., 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,…,m;j=1,2,…,n.\)

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 tỉnh để 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 tỉnh để 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 ô).

Yêu cầu: 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×n≤10^6)\).

• \(m\) dòng tiếp theo, dòng thứ \(i\) ghi các số nguyên \(a_{i1},a_{i2},…,a_{in} (0≤a_ij≤10^9)\).

• \(m\) dòng cuối cùng, dòng thứ i ghi các số nguyên \(b_{i1},b_{i2},…,b_{in} (0≤b_ij≤10^9)\).

Kết quả:

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

Ràng buộc:

• Có 60% số test tương ứng với 40% số điểm của bài có \(m×n≤20.\)

• Có 40% số test tương ứng với 70% số điểm của bài có \(m,n≤300.\)

Sample Input

3 4
18 12 18 16 
15 12 1 10 
14 4 6 14 
3 9 14 19 
1 0 5 10 
4 6 18 2

Sample Output

87