#3426. 运输小猫 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

小S是农场主,他养了 M 只猫,雇了 P 位饲养员。

农场中有一条笔直的路,路边有 N 座山,从 1 到 N 编号。

第 i 座山与第 i-1 座山之间的距离为

饲养员都住在 1 号山。

有一天,猫出去玩。

第 i 只猫去 号山玩,玩到时刻 停止,然后在原地等饲养员来接。

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

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

饲养员在路上行走需要时间,速度为1 米/单位时间。

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

例如有两座相距为 1 的山,一只猫在 2 号山玩,玩到时刻 3 开始等待。

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

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

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

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

输入格式

第一行包含三个整数N,M,P。

第二行包含n-1个整数,

接下来M行,每行包含两个整数

输出格式

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

样例

样例输入

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

样例输出

3

数据范围与提示

,

,

,

,

,