#212. Cats Transport

Cats Transport

题目描述

n 个车站排成一条线,管理员从1号站出发,沿路线行进并收走到达各站的猫。猫 j 在时刻 tj 到达 hj 站。每名管理员可自行选择出发时刻,沿路按规定站间耗时行进,不能在站内等待。猫由经过时已到站的管理员带走。安排 p 名管理员,最小化所有猫等待时间之和。

输入格式

首行 n、m、p。第二行 n−1 个相邻车站距离(即行进时间)。接下来 m 行 hj、tj。

输出格式

输出全部 m 只猫的最小等待时间总和。

样例输入

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

样例输出

3

题意整理;原题与输入输出格式对照。