#P20125. 「NOIP2011」观光公交

「NOIP2011」观光公交

题目描述

风景迷人的小城 Y 市,拥有 nn 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。

观光公交车在第 00 分钟出现在 11 号景点,随后依次前往 2,2, 3,3, ,\dots, nn 号景点。从第 ii 号景点开到第 i+1i+1 号景点需要 DiD_i 分钟。任意时刻,公交车只能往前开,或在景点处等待。

设共有 mm 个游客,每位游客需要乘车 11 次从一个景点到达另一个景点,第 ii 位游客在 TiT_i 分钟来到景点 AiA_i,希望乘车去景点 BiB_i (Ai<Bi)(A_i<B_i)。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。

一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 kk 个氮气加速器,每使用一个加速器,可以使其中一个 DiD_i11。对于同一个 DiD_i 可以重复使用加速器,但是必须保证使用后 Di0D_i\geq0

那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

输入格式

11 行是 33 个整数 n,m,kn, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

22 行是 n1n-1 个整数,每两个整数之间用一个空格隔开,第 ii 个数表示从第 ii 个景点开往第 i+1i+1 个景点所需要的时间,即 DiD_i

33 行至 m+2m+2 行每行 33 个整数 Ti,Ai,BiT_i, A_i, B_i,每两个整数之间用一个空格隔开。第 i+2i+2 行表示第 ii 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

输出格式

共一行,包含一个整数,表示最小的总旅行时间。

样例

3 3 2
1 4
0 1 3
1 1 2
5 2 3
10

D2D_2 使用 22 个加速器,从 22 号景点到 33 号景点时间变为 22 分钟。

公交车在第 11 分钟从 11 号景点出发,第 22 分钟到达 22 号景点,第 55 分钟从 22 号景点出发,

77 分钟到达 33 号景点。

11 个旅客旅行时间 70=77-0 = 7 分钟。

22 个旅客旅行时间 21=12-1 = 1 分钟。

33 个旅客旅行时间 75=27-5 = 2 分钟。

总时间 7+1+2=107+1+2 = 10 分钟。

数据范围与提示

对于 8%8\% 的数据,k=0k=0

对于 16%16\% 的数据,k=1k=1

对于 32%32\% 的数据,2n502 \leq n \leq 50m1000m \leq 1000k20k \leq 20Di10D_i \leq 10Ti500T_i \leq 500

对于 48%48\% 的数据,n100n \leq 100m1000m \leq 1000k100k \leq 100Ti104T_i \leq 10^4

对于 80%80\% 的数据,n1000n \leq 1000m104m \leq 10^4k105k \leq 10^5Di100D_i \leq 100Ti105T_i\leq 10^5

对于 100%100\% 的数据,1n,m1051 \leq n,m \leq 10^50k5×1060 \leq k \leq 5\times 10^60Di10000 \leq D_i \leq 10000Ti1060 \leq T_i \leq 10^6