#2396. 「JOISC 2017 Day 3」长途巴士

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

题目描述

题目译自 JOISC 2017 Day3 T1「長距離バス / Long Distance Coach

某长途巴士发车时刻为 0 ,到达终点的时刻为 X 。车上装有饮水机,乘客和司机可以在车上装水喝。
途中有 N 个服务站,依次编号为 1\ldots N 。巴士到达服务站 i(1\le i\le N) 的时间是 S_i
发车前,水箱是空的。在发车前你可以给饮水机加水,在服务站时也可以给饮水机加水,但是都要钱,水价为每升 W 円。假设水箱容量无限。

本次巴士有 M 名乘客(不含司机),乘客均在起点上车,不会中途下车。乘客 j(1\le j\le M) 在时刻 kT+D_j(k=0,1,2,\ldots) 需要装 1 升水,在其他时刻不装水。保证 1≤ D_j < T
司机在时刻 kT(k=0,1,2,\ldots) 需要装 1 升水,在其他时刻不装水。如果到终点之前,某一名乘客想装水时饮水机没水了,这名乘客会怒而下车,此时需要向这名乘客退 C_j 円。如果到终点之前,司机想装水时没水了,司机会怒而下车,这车就不开了。
保证不会出现两人在同一时刻需要装水的情况。保证在服务站或是到达终点时,不存在司机或乘客需要喝水。

我们希望花销(买水的总费用与退的所有车费之和)尽可能小,并且把车开到终点。试求至少需要花销多少円。

输入格式

第一行有五个整数 X, N, M, W, T
在接下来的 N 行中,第 i 行有一个整数 S_i 。 在接下来的 M 行中,第 j 行有两个整数 D_j, C_j

输出格式

一行,一个整数,表示最少的花销。

样例

样例输入 1

19 1 4 8 7
10
1 20
2 10
4 5
6 5

样例输出 1

103

样例解释 1

  • 出发时装了 7 升水;
  • 在时刻 0, 1, 2, 4, 6 ,司机与乘客 1, 2, 3, 4 先后装水,饮水机剩 2 升水;
  • 在时刻 7,8 ,司机和乘客 1 先后装水,饮水机没水了;
  • 在时刻 9 ,乘客 2 需要装水,但是饮水机没水了,因此乘客 2 下车,需要向其退款;
  • 在时刻 10 ,车到了服务站,向饮水机加 4 升水,此时饮水机剩余 4 升水;
  • 在时刻 11,13,14,15 ,乘客 3,4 ,司机和乘客 1 先后装水,饮水机没水了;
  • 在时刻 18 ,乘客 3 需要装水,但是饮水机没水了,因此乘客 3 下车,需要向其退款;
  • 在时刻 19 ,车到达终点,总计花销为 8\times(7+4)+(10+5)=103 ,可以证明这是最小花销。

样例输入 2

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

样例输出 2

547

样例输入 3

1000000000000 1 1 1000000 6
999999259244
1 123456789

样例输出 3

333333209997456789

数据范围与提示

对于所有数据, 1\le T\le X\le 10^{12}, 1\le N, M \le 2\times 10^5, 1\le W\le 10^6, 1\le S_i< X(1\le i\le N), 1\le D_j < T, 1\le C_j\le 10^9(1\le j\le M) 。保证 D_j 两两不同。

子任务 分值 N,M
1 16 N,M\le 8
2 30 N,M\le 100
3 25 N,M\le 2000
4 29 N,M\le 2\times 10^5