← 返回题目列表

Codeforces · 366/E

E. 迪玛和魔法吉他

中文机器翻译题面 查看原题

迪玛非常爱伊娜。他决定为她写一首歌。 Dima 有一把神奇的吉他,有 n 个琴弦和 m 个音品。迪马让吉他发出这样的声音:要演奏一个音符,他需要将一根琴弦固定在一个音品上,然后拉动琴弦。当 Dima 拉动第 i 根弦并将其固定在第 j 品上时,吉他会发出一个音符,我们将其表示为 aij。我们知道 Dima 的吉他可以发出 k 个不同的音符。有些笔记可能可以通过多种方式产生。换句话说,在 (i, j) ≠ (p, q) 时 aij = apq 是可能的。

Dima 已经写了一首歌——一系列 s 音符。为了演奏这首歌,您需要在吉他上连续发出歌曲中的音符。您可以以任何可用的方式生成每个注释。迪马明白演奏一首歌有很多种方式,他希望演奏得尽可能复杂(尝试像科宾那样)。

我们将把播放歌曲的方式表示为 (xi, yi) (1 ≤ i ≤ s) 序列对,这样第 yi 个品格上的第 xi 个字符串会产生歌曲中的第 i 个音符。在 (x1, y1) 和 (x2, y2) 对之间移动的复杂性等于 $${ \big | } x _ { 1 } - x _ { 2 } { \big | }$$ + $$\左| y_{1} - y_{2} \right|$$。播放歌曲的方式的复杂性是在相邻对之间移动的最大复杂性。

帮助迪马确定播放他的歌曲的方式的最大复杂性!这家伙看起来一定很酷!

输入

输入的第一行包含四个整数 n、m、k 和 s (1 ≤ n、m ≤ 2000、1 ≤ k ≤ 9、2 ≤ s ≤ 105)。

接下来是 n 行,每行包含 m 个整数 aij (1 ≤ aij ≤ k)。第 i 行第 j 列中的数字 (aij) 表示吉他在第 i 弦和第 j 品上产生的音符。

输入的最后一行包含 s 个整数 qi (1 ≤ qi ≤ k) — 歌曲的音符序列。

输出

在一行中打印一个数字——歌曲的最大可能复杂度。

示例

输入 #1

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

输出 #1

8

输入 #2

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

输出 #2

4