22438번 - TiMe Table 다국어

문제

ある学生は朝にいつも乗る通学バスで,あることに気がついた. そのバスの利用者がいつも同じなのだ. 気になってバスに乗っている利用者たちに聞いてみると,毎日決まった時刻にバス停に来ているようである. それなら,乗客にとってもっとよいバスの時間割があるのではないかとその学生は考えた.

学生の乗る通学路には,バスの営業所から終点までに$S$個のバス停が一直線に並んでいる.(営業所はバス停には含まれないが,終点はバス停に含まれる.) 各バス停には,営業所から近い方から順に1ドル$ から $S$ までの番号が付けられている. 営業所と $i$ 番目のバス停の距離は $x_i$ である. バスはまず営業所を出発し,それから $x_i$ 経った後に $i$ 番目のバス停に到着する. バス停には $N$ 人の利用者がやって来る. $i$ 番目の利用者は時刻 $t_i$ にバス停 $p_i$ にやって来る.

この通学路には1日にちょうど $M$ 本のバスが営業所から終点まで走ることになっている. バスはバス停に止まると,そのバス停で待っていた利用者を全員回収して,次のバス停に向かう. バス停で利用者を回収する時間は無視出来ると仮定する. いま各バスが営業所から出発する時刻を自由に決めることができるとき,利用者の待ち時間の和を最小化しよう.

입력

入力は以下の形式で与えられる.

$S$ $N$ $M$

$x_1$ $...$ $x_S$

$t_1$ $p_1$

$...$

$t_N$ $p_N$

출력

待ち時間の和の最小値を一行に出力せよ.

제한

• 1ドル ≤ S,   N,   M ≤ 2000$
• 1ドル ≤ x_1 < x_2 < …< x_S ≤ 10^4$
• 0ドル ≤ t_i ≤ 10^4$
• 1ドル ≤ p_i ≤ S$
• 入力値はすべて整数である.

힌트