問題文

物理好き君はスタンプラリーに参加しようとしています。

$1$ から $N$ までの番号が付けられた $N$ 個の場所にはそれぞれ異なるスタンプが設置されており、 そのうち相異なる $M$ 個以上のスタンプを集めることで景品を受け取る権利が得られます。
ただし、景品を受け取ることができるのは $K$ 個の場所 $A_{1}, \dots, A_{K}$ のみです。

場所 $i$ から場所 $j$ へ移動するためには $T_{i, j}$ だけ時間がかかります。
$T_{i, j}$ は次の $3$ つの条件を満たすものとします。

• $T_{i, i} = 0 \ (1 \leq i \leq N)$
• $1 \leq T_{i, j} \leq 10^{5} \ (1\leq i, j \leq N, i \ne j)$
• $T_{i, j} \leq T_{i, k} + T_{k, j} \ (1 \leq i, j, k \leq N)$

スタンプラリーを始める場所を自由に選べるとき、景品を受け取るまでにかかる時間の最小値を求めてください。

なお、スタンプラリーを始めた場所と景品を受け取る場所でもスタンプを押すことができます。
また、移動にかかる時間のみを考慮すればよく、スタンプを押す時間と景品を受け取るためにかかる時間は無視できるものとします。

制約

• 入力は全て整数
• $1 \leq N \leq 16$
• $1 \leq M \leq \min(N, 5)$
• $1 \leq K \leq N$
• $1 \leq A_{1} < A_{2} < \dots < A_{K} \leq N$
• $T_{i, i} = 0 \ (1 \leq i \leq N)$
• $1 \leq T_{i, j} \leq 10^{5} \ (1\leq i, j \leq N, i \ne j)$
• $T_{i, j} \leq T_{i, k} + T_{k, j} \ (1 \leq i, j, k \leq N)$

入力

$N\ M \ K$
$A_{1} \ \dots \ A_{K}$
$\begin{matrix} 
  T_{1, 1} & \dots  & T_{1, N} \\
  \vdots & \ddots & \vdots \\
  T_{N, 1} & \dots  & T_{N, N}
\end{matrix}$

出力

景品を受け取るまでにかかる時間の最小値を出力してください。

サンプル

3 2 1
3
0 1 1
1 0 1
1 1 0

1

5 1 3
1 2 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

0

5 3 4
1 2 4 5
0 4 4 7 2
7 0 7 6 9
4 7 0 4 6
1 4 5 0 3
6 2 4 5 0

3