Đội Hợp Xướng Hogwarts

Giáo sư Filius Flitwick đang chuẩn bị cho buổi biểu diễn của Đội Hợp Xướng Hogwarts. Ông cần sắp xếp các ca sĩ vào một đội hình dạng lưới $N\times M$ (gồm $N$ hàng và $M$ cột).

Mỗi ca sĩ thuộc một trong $K$ loại giọng hát (đánh số từ $1$ đến $K$). Khi hai ca sĩ đứng cạnh nhau (chung cạnh theo chiều ngang hoặc dọc), sẽ phát sinh một độ bất hòa âm phụ thuộc vào loại giọng của họ. Cụ thể, nếu ca sĩ loại giọng $a$ đứng cạnh ca sĩ loại giọng $b$, độ bất hòa âm là $D_{a,b}$.

Ma trận bất hòa âm $D$ có kích thước $K\times K$ và không nhất thiết đối xứng - nghĩa là $D_{a,b}$ có thể khác $D_{b,a}$. Độ bất hòa âm giữa hai ô kề nhau được tính từ ô bên trái sang phải (theo chiều ngang) và từ ô bên trên xuống dưới (theo chiều dọc). Cụ thể:

• Với hai ô $(i,j)$ và $(i,j+1)$: bất hòa âm là $D_{g_{i,j},g_{i,j+1}}$
• Với hai ô $(i,j)$ và $(i+1,j)$: bất hòa âm là $D_{g_{i,j},g_{i+1,j}}$

trong đó $g_{i,j}$ là loại giọng được gán cho ô $(i,j)$.

Giáo sư Flitwick muốn gán mỗi ô trong lưới một loại giọng (mỗi loại giọng có thể được dùng nhiều lần) sao cho tổng độ bất hòa âm giữa tất cả các cặp ô kề nhau là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $K$ - kích thước lưới và số loại giọng hát.
• $K$ dòng tiếp theo, mỗi dòng chứa $K$ số nguyên, mô tả ma trận bất hòa âm $D$. Dòng thứ $a$ ($1\le a\le K$), số thứ $b$ là $D_{a,b}$.

Dữ liệu ra

In ra một số nguyên duy nhất - tổng bất hòa âm nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le N\le 1000$
• $1\le M\le 7$
• $1\le K\le 4$
• $0\le D_{a,b}\le 1000$

Ví dụ