3701: 猫运输

Zxr960115是一个大农场的所有者。他喂养可爱的猫咪并使用喂食器。这条农场有一条直道，沿着道路有一座山丘，从左到右从1到n编号。山i和（i-1）之间的距离是di米。馈线住在山1。

有一天，猫出去玩了。猫我去山上旅行，在时间ti结束旅行，然后在山上等待喂食器。喂食者必须带走所有的猫。每个喂食器直接从山1到n直接在山上等待，并在每个山上带走所有等待的猫。喂食器以每单位时间1米的速度行走，并且足够强大，可以随心所欲地捕获尽可能多的猫。

例如，假设我们有两个山丘（d2 = 1）和一只猫在山丘2（h1 = 2）的时间3完成旅行。然后如果喂食器在时间2或时间3离开山丘1，他可以抓住这只猫，但是如果他在时间1离开山丘1他就不能接受它。如果喂食器在时间2离开小山1，则猫等待他0个时间单位，如果喂食器在时间3离开小山1，则猫等待他1个时间单位。

您的任务是安排从山坡1离开每个喂食器的时间，以便最小化所有猫的等待时间总和。

输入的第一行包含三个整数n，m，p（2≤n≤105,1≤m≤105,1≤p≤100）。

第二行包含n - 1个正整数d2，d3，...，dn（1≤di<104）。

接下来的m行中的每一行包含两个整数hi和ti（1≤hi≤n，0≤ti≤109）。

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

请不要在％С++中写入％lld说明符来读取或写入64位整数。 优选使用cin，cout流或％I64d说明符。

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

3