E. Дима болон шидэт гитар

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дима Иннад маш их хайртай. Тэр бүсгүйдээ дуу бичихээр шийджээ. Димад $n$ утастай $m$ ладтай шидэт гитар байдаг. Дима гитараараа ая тоглохын тулд утаснуудын нэгийг ладнуудын нэг дээр дарж утсыг татдаг. Дима $i$ дэх утсыг $j$ дэх ладан дээр дарж байгаад утсыг татвал дугарах нотыг $a_{ij}$ гэж тэмдэглэе. Бид Димагийн гитарыг $k$ ширхэг ялгаатай нот дугаргаж чадахыг мэддэг. Зарим нотнууд хэд хэдэн янзаар тоглогдох боломжтой юм. Өөрөөр хэлбэл ($i, j$) $≠$ ($p, q$) үед $a_{ij} = a_{pq}$ байх боломжтой.

Дима $s$ ширхэг нотны дарааллаас бүтсэн дуугаа аль хэдийн бичсэн байна. Дууг тоглохын тулд та гитараар дууны нотнуудыг дараалуулан тоглох хэрэгтэй. Та нот бүрийг дурын боломжит хувилбараар тоглож болно. Дима дууг тоглох олон хувилбар байгааг ойлгосон бөгөөд тэрээр дуугаа аль болох ярвигтай харагдах байдлаар тоглохыг хүсчээ (Кобэйн шиг царайлахыг хичээнэ).

Бид дууг тоглох хувилбарыг ($x_i, y_i$) ($1 ≤ i ≤ s$) хосуудаар илэрхийлэх бөгөөд $y_i$ дүгээр ладан дээрхи $x_i$ дүгээр утас дууны $i$ дэх нотыг тоглоно. ($x_1, y_1$) ба ($x_2, y_2$) хосуудын хоорондох ярвигтай байдлын хэмжээ +-тэй тэнцэнэ. Дууг тоглох хувилбарын ярвигтай байдлын хэмжээ нь зэргэлдээ нотуудын хооронд шилжих үйлдлийн ярвигтай байдлуудын хамгийн их утга юм.

Димад энэ дууг тоглох хамгийн ярвигтай замыг тодорхойлоход туслаарай! Залуу янзтай харагдах хэрэгтэй байна шүү дээ!

Оролт

Оролтын хамгийн эхний мөр $n$, $m$, $k$ ба $s$ ($1 ≤ n, m ≤ 2000$, $1 ≤ k ≤ 9$, $2 ≤ s ≤ 10^5$) гэсэн 4 бүхэл тоо агуулна.

Дараагийн $n$ мөрүүд тус бүр $m$ ширхэг $a_{ij}$ ($1 ≤ a_{ij} ≤ k$) бүхэл тоонуудаг агуулна. $i$ дүгээр мөр $j$ дүгээр багана дахь тоо ($a_{ij}$) нь гитар $i$ дүгээр утас $j$ дүгээр ладан дээр дугарч байгаа нотыг илэрхийлж байгаа юм.

Оролтын сүүлийн мөр дууны нотнуудын дараалал болох $s$ ширхэг $q_i$ ($1 ≤ q_i ≤ k$) бүхэл тоонуудыг агуулна.

Гаралт

Дууг тоглох ярвигтай байдлийн хамгийн их боломжит утга болох ганц тоог ганц мөрөнд хэвлэнэ.

Орчуулсан: Энхдүүрэн

Жишээ тэстүүд

Оролт
4 6 5 7
3 1 2 2 3 1
3 2 2 2 5 5
4 2 2 2 5 3
3 2 2 1 4 3
2 3 1 4 1 5 1
Гаралт
8
Оролт
4 4 9 5
4 7 9 5
1 2 1 7
8 3 4 9
5 7 7 2
7 1 9 2 5
Гаралт
4
Сэтгэгдлүүдийг ачааллаж байна...