問題 D : 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
• 入力値はすべて整数である.

入出力例

入力例 1

2 2 1
1 5
0 1
0 2

出力例 1

4

入力例 2

2 3 2
1 15
0 1
5 1
5 2

出力例 2

5

入力例 3

4 8 1
6 38 105 390
14 1
4 2
39 3
89 2
32 4
1 1
25 1
60 4

出力例 3

1123