Farmer John плывёт за легендарным кладом на одном из $N$ островов $(1 \le N \le 100)$ Cowribbean Sea, с номерами $1,\ldots,N$.

По карте клад появится после пути от1 до $N$ через последовательность $A_{1}$, $A_{2}$, ..., $A_{M}$ из $M$ островов $(2 \le M \le 10,000)$. Эти и другие можно посещать вне порядка и повторно, но путь должен содержать $A_{i}$ в заданном порядке.

FJ избегает пиратов и знает опасность $(0 \le danger \le 100,000)$ между каждой парой островов. Общая опасность — сумма по всем пройденным путям.

Найдите наименее опасный маршрут к кладу с условием карты.

Входные данные

• Строка1: два целых через пробел, $N$ и $M$.
• Строки $2,\ldots,M+1$: строка $i+1$ задаёт обязательный $i_{th}$ остров целым $A_{i}$.
• Строки $M+2,\ldots,N+M+1$: строка $i+M+1$ содержит $N$ целых через пробел, опасности от $i$ к1, 2, ..., $N$. $i$-е всегда0.

Выходные данные

• Строка1: минимальная опасность получения клада.

Примеры

Входные данные 1

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

Выходные данные 1

7

Примечание

3 острова и4 визита:1, 2, снова1, затем3. Пути(1,2), (2,3), (3,1) и обратные опасны на5, 2, 1.

Путь1, 3, 2, 3, 1, 3 даёт опасность7 и нужную последовательность1, 2, 1, 3. Избегаем опасного пути1–2.

Автор задачи: Jeffrey Wang, 2007