택배 배달

한 배달 기사는 매일 배달해야 할 위치 목록을 받는다. 목록에 적힌 순서대로 모든 물품을 배달해야 한다.

도시는 R*C개의 칸으로 나뉘어 있다. 행은 위에서부터 1번부터 R번까지, 열은 왼쪽에서부터 1번부터 C번까지 번호가 붙어 있다.

기사는 현재 칸에서 왼쪽 또는 오른쪽으로 한 칸 이동할 수 있다. 위나 아래로 이동하려면 반드시 첫 번째 열 또는 마지막 열에 있어야 하며, 그 열에서만 인접한 행으로 이동할 수 있다.

배달은 가장 왼쪽 위 칸 (1, 1)에서 시작한다. 기사는 처음부터 모든 물품을 가지고 출발하므로, 배달 중이거나 모든 배달을 마친 뒤 출발지로 돌아올 필요가 없다.

각 칸을 지나갈 때 걸리는 시간이 주어진다. 시작 칸을 포함하여 실제로 지나가는 모든 칸의 시간이 더해진다. 모든 물품을 순서대로 배달하는 데 필요한 최소 시간을 구하라.

첫째 줄에 도시의 크기 R과 C가 주어진다. (1 <= R <= 2000, 1 <= C <= 200)

다음 R개 줄에는 각 칸을 지나가는 데 걸리는 시간이 주어진다. 각 시간은 0 이상 5000 이하의 정수이다.

다음 줄에는 배달해야 하는 물품의 수 D가 주어진다. (1 <= D <= 200000)

다음 D개 줄에는 물품을 배달해야 하는 칸의 좌표가 배달 순서대로 주어진다. 같은 칸이 여러 번 나올 수 있지만, 연속해서 같은 칸이 주어지지는 않는다.

모든 물품을 순서대로 배달하는 데 걸리는 최소 시간을 출력한다.

첫 번째 공개 테스트에서는 다음 경로로 이동할 수 있다.

(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3), (2, 2)

이때 걸리는 총 시간은 1+2+1+0+1+2+2+2+1+2+3 = 17이다.