KAIST đang cạn kiệt ngân sách — họ cần tiền! Họ cho rằng các ký túc xá quá sang trọng so với các tòa nhà khác của KAIST; họ dự định bán tất cả các tòa nhà ký túc xá và xây dựng một tòa nhà mới hoàn toàn không có tính thẩm mỹ.

Ký túc xá mới sẽ có dạng lưới — không thể nhàm chán hơn thế này — với kích thước $N \times M$, mỗi ô là một phòng để sinh viên sinh sống. Chúng ta sẽ thêm một số cửa sổ vì muốn sinh viên nhận được chút ánh sáng mặt trời vào ban ngày!

Chúng ta dự định có chính xác $w_{i,j}$ cửa sổ trong phòng $(i, j)$. Mỗi phòng được bao quanh bởi 4 cạnh đơn vị của lưới. Một cửa sổ có thể được xây dựng trên một cạnh đơn vị của lưới, và tối đa một cửa sổ có thể được xây dựng trên mỗi mặt của một cạnh đơn vị — vì vậy mỗi ô có từ 0 đến 4 cửa sổ. Cửa sổ là loại một chiều: một cửa sổ ở mặt đối diện của một cạnh đơn vị không được tính là cửa sổ trong phòng đó.

Thật không may, sinh viên sẽ cảm thấy rất khó chịu khi không gian riêng tư của họ bị người khác nhìn thấy qua cửa sổ. Tổng sự khó chịu là số cặp sinh viên $\{a, b\}$ sao cho $a$ và $b$ có thể nhìn thấy không gian riêng tư của nhau qua cửa sổ.

Nói cách khác, nếu một cạnh đơn vị có cửa sổ ở cả hai mặt, tổng sự khó chịu sẽ tăng thêm bằng tích số lượng người sống trong hai phòng chia sẻ cạnh đó.

Bạn được cho $w_{i,j}$, số lượng cửa sổ dự kiến cho phòng $(i, j)$, và $p_{i,j}$, số lượng người sống trong phòng $(i, j)$. Nhiệm vụ của bạn là tìm tổng sự khó chịu tối thiểu có thể đạt được bằng cách sắp xếp các cửa sổ một cách hợp lý.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$: kích thước của lưới. Mỗi dòng trong $N$ dòng tiếp theo chứa $M$ số nguyên cách nhau bởi dấu cách $p_{i,j}$. Mỗi dòng trong $N$ dòng tiếp theo chứa $M$ số nguyên cách nhau bởi dấu cách $w_{i,j}$.

• $1 \le N \le 50$
• $1 \le M \le 50$
• $1 \le p_{i,j} \le 1000$ ($1 \le i \le N, 1 \le j \le M$)
• $0 \le w_{i,j} \le 4$ ($1 \le i \le N, 1 \le j \le M$)

Dữ liệu ra

In ra một số nguyên duy nhất: tổng sự khó chịu tối thiểu.

Ví dụ

Dữ liệu vào 1

4 3
1 7 10
7 2 8
7 9 10
4 6 4
3 3 3
3 2 4
4 3 4
2 2 3

Dữ liệu ra 1

178

Dữ liệu vào 2

4 3
2 2 9
9 8 4
8 4 5
7 5 2
0 1 0
1 0 1
0 0 1
0 1 0

Dữ liệu ra 2

0