题目描述

有一个学生早上经常坐公交车，注意到了一件事：那辆公交车的乘客数量总是一样的！他问了一下坐公交车的乘客们，发现他们每天都在同样的时间来公交车站。这样的话，那个学生想：对乘客来说不是有更好的公交车时间表吗？

在这名学生上学的路上，从调度站到终点站，有$S$个站点行程一条直线（调度站不包括在公交车站，终点站包括在公交车站）。各个车站离调度站的距离由近及远依次编号为$1$到$S$。营业所和第$i$个公交车站的距离是$x_i$。公共汽车先从调度站出发，然后过一会就到了第$i$站。车站来了$N$个乘客。第$i$个乘客是时刻$t_i$车站$p_i$到来的。

这条上学路一天正好有$M$趟公交车从调度站开到终点。公交车一停靠在车站，就把在那个车站等着的所有乘客都接上车，奔向下一个车站。假设车站接乘客上车的时间可以忽略不计，现在各公交车可以决定从调度站出发的时间，那么，请你把乘客的等待时间之和最小化吧！

输入格式

$S$ $N$ $M$

$x_1$ $...$ $x_S$

$t_1$ $p_1$

$...$

$t_N$ $p_N$

输出格式

一行一个整数，表示乘客的最小等待时间。

数据范围

$1≤S,N,M ≤ 2000；$

$1≤x_1＜x_2＜……＜x_s≤10^4$

$0≤t_i≤10^4$

$1≤p_i≤S$

$输入的数字都是整数。$

样例2解析

在这个例子中，最适合使公共汽车在时刻$-10$和$4$出发。