迪玛非常爱伊娜。他决定为她写一首歌。 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