CF366E Dima and Magic Guitar

Dima 非常爱 Inna，他决定为她写一首歌。Dima 有一把神奇的吉他，共有 $n$ 根弦和 $m$ 个品格。Dima 让吉他发声的方法如下：为了弹奏一个音符，他需要在某根弦的某个品格按下，然后拨动该弦。当 Dima 按下第 $i$ 根弦的第 $j$ 个品格并拨弦时，吉他会发出一个音符，记作 $a_{ij}$。已知 Dima 的吉他最多可以发出 $k$ 种不同的音符。可能有些音符可以通过多种方式弹奏，也就是说可能存在 $a_{ij}=a_{pq}$，其中 $(i, j) \neq (p, q)$。 Dima 已经写好了一首歌——它是一串长度为 $s$ 的音符。为了演奏这首歌，需要依次在吉他上弹奏出这串音符中的每一个音符。对于每一个音符，你可以选择任意一种可用的弹奏方式。Dima 发现演奏同一首歌有许多不同的方式，他想让演奏看起来尽可能复杂一些（表现得像 Cobein 一样）。 我们用一个序列 $(x_i, y_i) (1 \leq i \leq s)$ 表示吉他的弹奏方式，表示用第 $x_i$ 根弦的第 $y_i$ 个品格弹奏出第 $i$ 个音符。两次弹奏 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的复杂度为 $|x_1 - x_2| + |y_1 - y_2|$。一种演奏方式的复杂度定义为相邻两个弹奏之间复杂度的最大值。 请帮助 Dima 计算出吉他这首歌可能的最大复杂度是多少！这个小伙儿一定要看起来很酷！

第一行包含四个整数 $n$、$m$、$k$ 和 $s$，表示弦数、品格数、音符种类数、歌曲长度 $(1\leq n,m\leq 2000, 1\leq k\leq 9, 2\leq s\leq 10^5)$。 接下来 $n$ 行，每行 $m$ 个整数，表示 $a_{ij}$，第 $i$ 根弦第 $j$ 个品格发出的音符 $(1\leq a_{ij}\leq k)$。 最后一行包含 $s$ 个整数 $q_i$ $(1\leq q_i\leq k)$，表示歌曲的音符序列。

输出一个整数，表示这首歌可能的最大复杂度。

由 ChatGPT 5 翻译