U137694.环形车站

1 列车到达车站先下客再上客
2 列车有最大载客量 V 上车时如果当前车上已有 x 人则最多还能上 V 减 x 个人多出来的乘客无法上车直接舍弃
3 列车行驶完选定站数后强制清空全部乘客本次行程结束之后可以立刻选任意车站重新发车
4 总时间一共要跑完 m 轮完整的环形
求 m 轮跑完之后总共成功接载的乘客最大数量
输入格式
第一行三个整数 n k V m
2 小于等于 n 小于等于 800 1 小于等于 k 小于等于 n 1 小于等于 V 小于等于 2000 1 小于等于 m 小于等于 100000
接下来 n 行每行两个整数 a_i b_i 代表第 i 号车站的上客下客人数 0 小于等于 a_i b_i 小于等于 1000
输出格式
输出一个整数最大总接载乘客数

3 2 5 2
8 2
3 4
6 1

22

1 把环复制一倍变为长度 2n 的链枚举所有起点
2 预处理 f s t 代表从 s 出发连续开到 t 站一趟可以接到多少乘客模拟上下客过程
3dp i 代表前 i 个车站可以得到的最大收益
4 求出单轮一轮的最大收益之后计算 m 轮总结果