Kho báu GCD

Ngày xửa ngày xưa, tại một vùng đất huyền bí, có một kho báu bị yểm bùa bởi một lời nguyền số học cổ xưa. Lời nguyền này được canh giữ bởi các con số, và chỉ những nhà toán học tài ba nhất mới có thể giải mã. Kho báu được chôn giấu trong một khu rừng rậm được chia thành \(N\) hàng và \(M\) cột, tạo thành một ma trận khổng lồ. Mỗi ô trong ma trận chứa một số nguyên dương, đại diện cho "năng lượng" của lời nguyền tại vị trí đó.

Truyền thuyết kể rằng, để phá giải lời nguyền và tìm ra kho báu, một nhà thám hiểm phải chọn một ma trận con (submatrix) trong khu rừng. Ma trận con này phải thỏa mãn hai điều kiện cực kỳ quan trọng:

• Ước chung lớn nhất (GCD) của tất cả các số nguyên trong ma trận con được chọn phải bằng 1. Đây là chìa khóa để "phá vỡ" lời nguyền.
• Tổng của tất cả các số nguyên trong ma trận con phải là nhỏ nhất có thể. Bởi vì, mỗi đơn vị năng lượng càng lớn thì lời nguyền càng khó giải.

Bạn là một nhà toán học trẻ đầy tài năng, và đã được giao nhiệm vụ giải cứu kho báu. Hãy tìm ma trận con thỏa mãn cả hai điều kiện trên và cho biết tổng giá trị của nó.

Input

Dữ liệu được cung cấp theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \le N, M \le 200\)), lần lượt là số hàng và số cột của ma trận ban đầu.
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên dương \(A_{i,j}\) (\(1 \le A_{i,j} \le 10^5\)), mô tả giá trị năng lượng tại ô \((i, j)\) của ma trận.

Output

In ra một số nguyên duy nhất là tổng nhỏ nhất của các phần tử trong ma trận con tìm được.

Example

3 3
2 6 6
6 6 6
6 6 3

47

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N, M \le 10\).
• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N, M \le 100\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại có \(N, M \le 200\).