Source : 信息学奥赛一本通-提高篇
Description
  ssoi是一个大农场主,他养了m只猫,聘请了p个饲养员。沿着农场的道路有n座山,从左到右依次编号为1到n。第i座山和第i-1座山的距离是d[i],饲养员都在第1座山。
  一天,小猫们都出去游玩,第i只猫游玩第h[i]座山,在t[i]时刻游玩结束,并在第h[i]座山等待饲养员去接它,所有猫都必须接回家。饲养员从第1座山出发走到第n座山,到达一座山时,将山上的猫接走,饲养员不会等待一只猫游玩结束,他只会接走正在等待的猫。饲养员的行走速度是1,在每座山接猫的时间忽略不计,他们非常有力,每次可以接走任意多只猫。
  例如,有两座山,d[2]=1,一只猫在第2座山(h[1]=2),在时间3游玩结束,如果饲养员离开在时间2或者时间3离开第1座山,他能接走这只猫,因为饲养员不需要等待这只猫,但是如果他在时间1离开第1座山,他不能接走这只猫。
  请安排饲养员的出发时间,使得所有猫的等待的时间总和最小。

Input
第一行,3个整数n,m,p (2≤ n≤ 10^5, 1 ≤ m≤ 10^5, 1 ≤ p≤ 100);
第二行,n-1个正整数d2,d3,...,dn (1≤ di<10^4);
接下来m行,每行两个整数hi和ti。(1≤ hi≤ n,0≤ ti≤ 10^9)。
Output
出共一行,一个整数,表示所有猫的最小等待时间。
Sample Input
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
Sample Output
3
Hint