Problem description
Dana jest tablica o N wierszach i N kolumnach. Komórka w i-tym wierszu i j-tej kolumnie ma początkowo pewien kolor ki, j. Twoim zadaniem jest przemalować tablicę tak, żeby dla danego K, oraz dla dowolnych i, j, x, y zachodziły następujące warunki:
- Jeżeli reszta z dzielenia przez K liczb (i+j) oraz (x+y) jest taka sama, to komórki (i,j) oraz (x,y) powinny mieć ten sam kolor.
- Jeżeli reszta z dzielenia przez K liczb (i+j) oraz (x+y) jest różna, to komórki (i,j) oraz (x,y) muszą mieć różne kolory.
Jednakże, zmiana koloru pojedynczej komórki o kolorze i w kolor j kosztuje ci, j. Kolor każdej komórki można zmienić co najwyżej raz. Jaki jest najmniejszy sumaryczny koszt przemalowania tablicy tak, żeby spełniała oba warunki?
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite N, K oraz C, oznaczające odpowiednio rozmiar tablicy, parametr K oraz liczbę kolorów. W następnych N wierszach znajduje się opis początkowego stanu tablicy. i-ty wiersz składa się z N liczb, ki, 1, …, ki, N, oznaczająca początkowe kolory w i-tym wierszu tablicy.
Potem następuje C wierszy opisujące koszta zmiany kolorów. W i-tym wierszu znajduje się C liczb ci, 1, …, ci, C, wartość ci, j określająca cenę zmiany koloru i w kolor j (odwrotna zmiana koloru może mieć inną cenę).
Wyjście
W jednym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą minimalny koszt przemalowania tablicy tak, by spełniała założenia zadania.
Ograniczenia
1 ≤ N ≤ 1 000, 1 ≤ C ≤ 10, 1 ≤ K ≤ C, 1 ≤ ki, j ≤ C, 1 ≤ ci, j ≤ 109.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | K = 1. | 26 |
| 2 | K = 2. | 31 |
| 3 | K = 3. | 32 |
| 4 | Brak dodatkowych ograniczeń. | 11 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Zmiana komórki (2,1) w kolor pierwszy oraz komórki (2,2) w kolor trzeci spowoduje, że warunki zadania zostaną spełnione minimalnym kosztem 5. |