import scala.io.StdIn._
object Main extends App {

  val Array(s, n, m) = readLine.trim.split(' ').map(_.toInt)
  val stops = readLine.trim.split(' ').map(_.toInt)
  val passengers = Array.tabulate(n){_ ⇒
    val Array(t, p) = readLine.trim.split(' ').map(_.toInt)
    t - stops(p - 1)
  }.sorted
  val waitingTimeSum = 0 +: passengers.map{_ - passengers.head}
  for (i ← waitingTimeSum.indices.tail) waitingTimeSum(i) += waitingTimeSum(i - 1)
  val memo = Array.fill(m){Array.fill(n + 1){-1}}
  for (i ← 0 to n) memo(0)(i) = waitTime(i, n - 1)
  for (i ← 1 until m) {
    memo(i)(n) = 0
    minTime(i)
  }
  println(memo.last.head)
  def minTime(busRest: Int): Long = {
    def rec(pMin: Int, pMax: Int, kMin: Int, kMax: Int): Unit = {
      if (pMin <= pMax) {
        val mid = (pMin + pMax) / 2
        val (r, k) = (math.max(mid, kMin) to math.min(n, kMax)).map{k ⇒ (memo(busRest - 1)(k + 1) + waitTime(mid, k), k)}.minBy(_._1)
        memo(busRest)(mid) = r
        rec(pMin, mid - 1, kMin, k)
        rec(mid + 1, pMax, k, kMax)
      }
    }
    rec(0, n - 1, 0, n - 1)
    memo(busRest).last
  }
  def waitTime(from: Int, to: Int): Int = {
    (passengers(to) - passengers.head) * (to - from + 1) - waitingTimeSum(to + 1) + waitingTimeSum(from)
  }
}
