题目描述

小S是农场主，他养了 $\red {M}$ 只猫，雇了 $\red {P}$ 位饲养员。

农场中有一条笔直的路，路边有 $\red {N}$ 座山，从 $\red {1}$ 到 $\red {N}$ 编号。

第 $\red {i}$ 座山与第 $\red {i-1}$ 座山之间的距离为 $\red {D_i}$ 。

饲养员都住在 $\red {1}$ 号山。

有一天，猫出去玩。

第 $\red {i}$ 只猫去 $\red {H_i}$ 号山玩，玩到时刻 $\red {T_i}$ 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 $\red {1 }$号山走到 $\red {N }$号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为$\red {1}$ 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 $\red {1 }$的山，一只猫在 $\red {2 }$号山玩，玩到时刻 $\red {3 }$开始等待。

如果饲养员从 $\red {1 }$号山在时刻 $\red {2 }$或 $\red {3 }$出发，那么他可以接到猫，猫的等待时间为 $\red {0 }$或 $\red {1}$。

而如果他于时刻 $\red {1}$ 出发，那么他将于时刻 $\red {2 }$经过 $\red {2 }$号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 $\red {1 }$号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式

第一行包含三个整数$\red {N}$，$\red {M}$，$\red {P}$。

第二行包含$\red {n-1}$个整数，$\red {D_2 ,D_3 ,…,D_N}$ 。

接下来$\red {M}$行，每行包含两个整数$\red {H_i}$和$\red {T_i}$ 。

输出格式

输出一个整数，表示所有猫等待时间的总和的最小值。

样例

输入样例

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

输出样例

3

提示

$\red {2≤N≤10^5}$,

$\red {1≤M≤10^5}$,

$\red {1≤P≤100}$,

$\red {1≤D_i <1000}$,

$\red {1≤H_i ≤N}$,

$\red {0≤T_i ≤10^9}$