import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val Array(m, n) = readLine.trim.split(' ').map(_.toInt)
    if (m == 0) return
    val d = readInt
    val sign = Array.tabulate(m){_ ⇒ Array.tabulate(n){_ ⇒ 0}}
    val road = Array.tabulate(m){h ⇒ Array.tabulate(n){w ⇒ Point(w, h).neighbor.filter(p ⇒ (0 until n).contains(p.x) && (0 until m).contains(p.y)).map(p ⇒ (p, d))}}
    for (_ ← 0 until readInt){
      val Array(c, k) = readLine.trim.split(' ')
      val Array(h, w) = c.split('-')
      sign(h.head - 'a')(w.toInt - 1) = k.toInt
    }
    for (_ ← 0 until readInt){
      val Array(f, t) = readLine.trim.split(' ')
      val Array(fh, fw) = f.split('-')
      val Array(th, tw) = t.split('-')
      val from = Point(fw.toInt - 1, fh.head - 'a')
      val to = Point(tw.toInt - 1, th.head - 'a')
      road(from.y)(from.x) = road(from.y)(from.x).filterNot(_._1 == to)
      road(to.y)(to.x) = road(to.y)(to.x).filterNot(_._1 == from)
    }
    for (_ ← 0 until readInt){
      val Array(f, t, add) = readLine.trim.split(' ')
      val Array(fh, fw) = f.split('-')
      val Array(th, tw) = t.split('-')
      val from = Point(fw.toInt - 1, fh.head - 'a')
      val to = Point(tw.toInt - 1, th.head - 'a')
      road(from.y)(from.x) = (to, d + add.toInt)::road(from.y)(from.x).filterNot(_._1 == to)
      road(to.y)(to.x) = (from, d + add.toInt)::road(to.y)(to.x).filterNot(_._1 == from)
    }
    val (from: Point, to: Point) = readLine.trim.split(' ').map{_.split('-')}.let{case Array(Array(fh, fw), Array(th, tw)) ⇒ (Point(fw.toInt - 1, fh.head - 'a'), Point(tw.toInt - 1, th.head - 'a'))}
    val queue = mutable.PriorityQueue()(Ordering.by[(Point, Point, Int), Int](_._3).reverse).also{q ⇒ q.enqueue((from, Point(from.x - 1, from.y), 0))}
    val isQueued = Array.tabulate(101){_ ⇒ Array.tabulate(m){_ ⇒ Array.tabulate(n){_ ⇒ Array.tabulate(4){_ ⇒ false}}}}.also{a ⇒ a(0)(from.y)(from.x)(Point(1, 0).toIndex) = true}
    while(queue.head._1 != to){
      val (current, prev, time) = queue.dequeue()
      for ((next, additional) ← road(current.y)(current.x) if next != prev && time + additional <= 100) {
        if (sign(next.y)(next.x) == 0 || (current.x == next.x && ((time + additional) / sign(next.y)(next.x)) % 2 == 0) || (current.y == next.y && ((time + additional) / sign(next.y)(next.x)) % 2 == 1)) {
          if (!isQueued(time + additional)(next.y)(next.x)((next - current).toIndex)) {
            isQueued(time + additional)(next.y)(next.x)((next - current).toIndex) = true
            queue.enqueue((next, current, time + additional))
          }
        }
      }
    }
    println(queue.head._3)
    queue.clear()
    solve
  }
  implicit class PointExtension(val value :Point) extends AnyVal {
    def toIndex: Int = if (value.x == 0) (value.y + 1) / 2 else (value.x + 1) / 2 + 2
  }
  case class Point(x: Int, y: Int){
    def neighbor: List[Point] = List(Point(x + 1, y), Point(x - 1, y), Point(x, y + 1), Point(x, y - 1))
    def -(that: Point): Point = Point(x - that.x, y - that.y)
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}


Measured memory_bytes: 81944