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座山，他不能接走这只猫。
  请安排饲养员的出发时间，使得所有猫的等待的时间总和最小。

第一行，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)。

出共一行，一个整数，表示所有猫的最小等待时间。