Cho bảng kích thước ~m\times n~. Ô ~(i,j)~ có giá trị ~a_{i,j}~. Robot bắt đầu từ ô ~(1,1)~ và chỉ được đi sang phải hoặc đi xuống để tới ô ~(m,n)~.

Chi phí của một ô bằng tổng các ước nguyên dương của ~a_{i,j}~ không kể chính nó. Robot trả phí cho các ô trên đường đi. Hãy tìm chi phí nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên dương ~m,n~.

~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên dương ~a_{i,j}~.

Output

In ra chi phí nhỏ nhất.

Subtask

• 20% số điểm: ~n=1~, ~a_{i,j} \le 10^3~.
• 20% số điểm: ~n=1~, ~10^3 \le a_{i,j} \le 10^6~.
• 20% số điểm: ~n=2~, ~a_{i,j} \le 10^6~.
• 20% số điểm: ~n>2~, ~a_{i,j} \le 10^6~.
• 20% số điểm: ~a_{i,j} \ge 10^7~, ~\max(a_{i,j})-\min(a_{i,j}) \le 10^6~.

Ví dụ

2 6
1 3 9 9 3 8
3 6 8 7 6 8

23