import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  solve()
  @tailrec def solve(): Unit = {
    val Array(w, h) = readLine.trim.split(' ').map(_.toInt)
    if (w == 0 && h == 0) return
    val field = new Field(Array.tabulate(h) { _ ⇒ readLine.trim.split(' ').map(_.toInt) })
    val costs = readLine.trim.split(' ').map(_.toInt)
    val operations = Array(Straight, Right, Back, Left)
    val memo = Array.fill(h) {Array.fill(w) {Array.fill(4) {Int.MaxValue}}}
    val queue = mutable.PriorityQueue()(Ordering.by[(Int, Robot), Int](_._1).reverse)
    memo(0)(0)(1) = 0
    queue.enqueue((0, InOperation(East, Coordinate(0, 0))))
    while (queue.nonEmpty) {
      val (cost, robot) = queue.dequeue()
      if (memo(robot.position.y)(robot.position.x)(robot.direction.toInt) == cost) {
        for (op ← operations.indices) {
          val c = if (operations(op) == field(robot.position)) 0 else costs(op)
          val next = robot.execute(operations(op))
          if (next.isInOperation && field.contains(next.position) && memo(next.position.y)(next.position.x)(next.direction.toInt) > cost + c) {
            memo(next.position.y)(next.position.x)(next.direction.toInt) = cost + c
            queue.enqueue((cost + c, next))
          }
        }
      }
    }
    println(memo.last.last.min)
    solve()
  }
  class Field(state: Array[Array[Int]]) {
    private val field = state.map{_.map{
      case 0 ⇒ Straight
      case 1 ⇒ Right
      case 2 ⇒ Back
      case 3 ⇒ Left
      case 4 ⇒ Halt
      case _ ⇒ ???
    }}
    def contains(coordinate: Coordinate): Boolean = field.indices.contains(coordinate.y) && field.head.indices.contains(coordinate.x)
    def apply(coordinate: Coordinate): Operation = field(coordinate.y)(coordinate.x)
    def isGoal(coordinate: Coordinate): Boolean = field.length == coordinate.y && field.head.length - 1 == coordinate.x
  }
  sealed trait Robot {
    val direction: Direction
    val position: Coordinate
    def execute(operation: Operation): Robot
    def isInOperation: Boolean
  }
  case class InOperation(direction: Direction, position: Coordinate) extends Robot {
    override def execute(operation: Operation): Robot = {
      operation match {
        case Halt ⇒ Stopped(direction, position)
        case _ ⇒ changeDirection(operation).moveForward
      }
    }
    private def moveForward: InOperation = InOperation(direction, position.move(direction))
    private[this] def changeDirection(operation: Operation): InOperation = {
      operation match {
        case Left ⇒ InOperation(direction.turnLeft, position)
        case Right ⇒ InOperation(direction.turnRight, position)
        case Back ⇒ InOperation(direction.turnBack, position)
        case _ ⇒ this
      }
    }
    override def isInOperation: Boolean = true
  }
  case class Stopped(direction: Direction, position: Coordinate) extends Robot {
    override def execute(operation: Operation): Robot = this
    override def isInOperation: Boolean = false
  }
  sealed trait Direction {
    def turnRight: Direction = Direction.fromInt(Direction.toInt(this) + 1)
    def turnLeft: Direction = Direction.fromInt(Direction.toInt(this) + 3)
    def turnBack: Direction = Direction.fromInt(Direction.toInt(this) + 2)
    def toInt: Int = Direction.toInt(this)
  }
  object Direction{
    private def fromInt(value: Int): Direction = {
      (value % 4 + 4) % 4 match {
        case 0 ⇒ North
        case 1 ⇒ East
        case 2 ⇒ South
        case 3 ⇒ West
        case _ ⇒ ???
      }
    }
    private def toInt(direction: Direction): Int = {
      direction match {
        case North ⇒ 0
        case East ⇒ 1
        case South ⇒ 2
        case West ⇒ 3
      }
    }
  }
  object North extends Direction
  object East extends Direction
  object South extends Direction
  object West extends Direction
  case class Coordinate(x: Int, y: Int) {
    def move(direction: Direction): Coordinate = {
      direction match {
        case North ⇒ Coordinate(x, y - 1)
        case East ⇒ Coordinate(x + 1, y)
        case South ⇒ Coordinate(x, y + 1)
        case West ⇒ Coordinate(x - 1, y)
      }
    }
  }
  sealed trait Operation
  object Straight extends Operation
  object Right extends Operation
  object Back extends Operation
  object Left extends Operation
  object Halt extends Operation
}



Measured memory_bytes: 130760