Trước tình hình trào lưu "trà xanh" ngày càng phức tạp và có xu hướng lây lan nhanh, các cô gái có người yêu ngày càng cảm thấy bất an trước nguy cơ mất người yêu vào tay những em gái vẻ ngoài hiền lành thảo mai nhưng bên trong thâm sâu hiểm ác. Là một trong số đó, Bích Phương bắt bạn trai của mình tham dự "thử thách trà xanh" để kiểm tra sự chung thủy của anh ta.

Tham gia thử thách này, bạn trai của Bích Phương –sửu nhi Ngu* V** L** (tên nhân vật được giữ bí mật nhằm tránh các xung đột đáng tiếc) phải đi trên một ma trận có dạng lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(0\) đến \(r - 1\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(0\) đến \(c - 1\) theo thứ tự từ trái qua phải. Tại mỗi ô của ma trận, có sẵn một em gái "trà xanh" trực sẵn, chờ cho L** đi vào sẽ tìm cách thả thính. Do Bích Phương chọn cho người yêu thử thách độ khó cao nhất, các em gái "trà xanh" đều rất cute và body siêu chuẩn. Cụ thể, em gái ở ô thuộc hàng \(i\) và cột \(j\) có độ hấp dẫn là \(b_{i, j}\).

Thử thách bắt đầu, L** được chọn một ô bất kì ở cột ngoài cùng bên trái (cột \(0\)) để đi vào. Tiếp sau đó, L** sẽ lần lượt đi qua các cột theo thứ tự từ trái qua phải, và kết thúc thử thách sau khi đã đi qua cột cuối cùng (cột \(c - 1\)). Tuy nhiên, có một ràng buộc: nếu L** đang ở ô thuộc hàng \(x\) và cột \(y\), ở bước tiếp theo L** chỉ có thể đi tới một trong ba ô thuộc hàng \(x^2 \bmod r\), \(x^3 \bmod r\) hoặc \(x^4 \bmod r\) và cột \(y + 1\).

Ví dụ, giả sử bảng có \(r = 7\) hàng, L** có thể đi từ ô \((3, 1)\) sang một trong ba ô \((2, 2)\), \((6, 2)\) và \((4, 2)\) vì \(3^2 \bmod 7 = 9 \bmod 7 = 2\), \(3^3 \bmod 7 = 27 \bmod 7 = 6\), \(3^4 \bmod 7 = 81 \bmod 7 = 4\); từ ô \((0, 2)\) L** chỉ có thể đi sang ô \((0, 3)\) vì \(0^2 \bmod 7 = 0^3 \bmod 7 = 0^4 \bmod 7 = 0\).

L** không quan tâm lắm đến việc thử thách thất bại hay thành công, nhưng L** không muốn gặp quá nhiều em gái xinh tươi thu hút ở trong đó vì sợ L** sẽ đau lòng nếu trót phải lòng các em mà không được gặp lại nữa. Như Lục Xu đã nói, Tình là mê luyến, khi gặp được chân tình thì sẽ là thiên đường. Tình là bi ai khi không gặp được người thì đau đớn đến tận xương tùy. Bởi vậy, các bạn hãy giúp L** tìm một đường đi vào mê cung trà xanh rồi thoát ra sao cho tổng độ cute của các em L** gặp trong đó là nhỏ nhất.

Các bạn hãy giúp L** giữ được con tym của mình không bị đập loạn nhịp nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \le r, c \le 2207)\) – số hàng và số cột của ma trận.
• \(r\) dòng tiếp theo, mỗi dòng chứa \(c\) số nguyên thể hiện độ cute của các em gái "trà xanh" ở trong ma trận.
  • Các số nguyên này có giá trị từ \(0\) đến \(10^6\).

Output

• In ra một số nguyên duy nhất là tổng độ cute nhỏ nhất của các em L** sẽ gặp trong ma trận.

Example

7 3
1 1 1
1 1 1
1 0 1
0 1 1
1 1 0
1 1 1
1 1 1

0

2 4
2 2 0 7
1 9 9 7

11

Scoring

• Subtask \(1\) (\(35\) điểm): \(r, c \le 12\)
• Subtask \(2\) (\(20\) điểm): \(r \le 3\)
• Subtask \(3\) (\(45\) điểm): Không có ràng buộc gì thêm.