标题

将以下文本翻译成中文

代码块

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

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

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

## 标题

### 输入形式

入力是以下的形式给出。

S N M
x1 ... xS
t1 p1
...
tN pN

### 输出形式

等待时间总和的最小值输出为一行。

### 约束条件

- 1 ≤ S,   N,   M ≤ 2000
- 1 ≤ x1 < x2 < …< xS ≤ 10^4
- 0 ≤ ti ≤ 10^4
- 1 ≤ pi ≤ 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

这个例子中，最优的选择是在时刻$-10$和$4$出发。

#### 输入示例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