AlgoLiga 2018

W świecie matematycznych cwaniaczków posiadanie porządnego łańcucha liczb na szyi to podstawa. Oczywiście nie może on być byle jaki. Szacunek na swojej płaszczyźnie można zdobyć wtedy i tylko wtedy gdy jesteśmy posiadaczami łańcucha składającego się wyłącznie z liczb pierwszych z przedziału [1;z]. Dodatkowo ciąg liczb tworzących łańcuch powinien być palindromem. Niestety kupno gotowego łańcucha spełniającego te założenia graniczy z cudem. Całe szczęście łańcuch można zmieniać. Każdy element ciągu możemy dowolną ilość razy przekształcać w inną liczbę z przedziału [1;z], oczywiście ponosząc przy tym koszty takiej zmiany.

Zakupiłeś właśnie n liczbowy łańcuch na szyję. Pytanie brzmi ile minimalnie pieniędzy będziesz musiał wydać na przekształcenia żeby Sigma i Pi nie śmiali się z Twojego zakupu?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby naturalne n ∈ [1;10⁵] i z ∈ [2;100] oznaczające odpowiednio ilość liczb naturalnych, z których zbudowany jest łańcuch oraz ich górny zakres. W kolejnych z wierszach znajduje się po z liczb z przedziału [0;10⁹]. Liczba w i-tym wierszu i j-tej kolumnie określa koszt przekształcenia liczby i w j. Dla i = j koszt zawsze wynosi 0. Zakładamy, że wiersze i kolumny numerowane są od 1. W ostatniej linii wejścia znajduje się n liczb z przedziału [1;z] oznaczających kolejne elementy ciągu tworzącego zakupiony przez Ciebie łańcuch.

Wyjście

Na wyjściu należy wypisać jedną liczbę naturalną, sumaryczny koszt przekształceń elementów łańcucha, tak aby składał się on wyłącznie z liczb pierwszych z przedziału [1;z] i był palindromem.

Przykład

Wejście

4 3
0 1 7
2 0 10
3 20 0
2 1 2 1

Wyjście

2

Wyjaśnienie

Najbardziej opłacalne jest przekształcenie liczb 1 w 2 kosztem 1 za każdą z nich.