3694: 门童(第四轮04)
题目描述
为了认识更多的异性朋友，牛牛在各类活动中做志愿者。这天， 牛牛在大型赛事 AUPC (Asia University Program Competition) 中担任志愿者，他的任务是在大厅 门口接待选手们。
接待的过程是漫长而枯燥的，牛牛把这一过程中自己的心情变化用一个整数来描 述，他称这个整数为他的开心度。大厅中有一个休息用的沙发，沙发到门口的距 离为L米。牛牛可以在门口到沙发间直线往返，他用四个参数x00, x01, x10, x11 来描 述他在门口，从门口向沙发走，从沙发向门口走和在沙发时的开心度变化。具体 来说，
1. 当牛牛站在门口时（即牛牛与门口的距离为0时）， 牛牛的开心度每秒减少x00;
2. 当牛牛从门口向沙发走去的时候，牛牛的开心度每秒减少x01 ;
3. 当牛牛从沙发向门口走去的时候，牛牛的开心度每秒减少x10 ;
4. 当牛牛躺在沙发上摸鱼的时候（即牛牛与沙发的距离为 0 时）， 牛牛的开心度每秒增加 x11 。
牛牛的移动速度固定是1米/秒。牛牛只有站在门口（即牛牛与门口的距离为0时） 才能接待选手，且因为牛牛手速惊人，接待选手可以看作是瞬间完成的。
为了能够快乐地摸鱼， 牛牛事先收集了一些信息： 一共有n名选手需要接待， 其中第i (1 ≤ i ≤ n)名选手会在时刻ti 到达大厅门口并等待接待，他的耐心值为pi , 友善值为fi，如果牛牛在时刻T (ti ≤ T ≤ ti + pi)接待第i 名选手，那么牛牛的开心 度会瞬间上升 fi × (ti + pi − T)， 但是如果第i名选手在时间段[ti, ti + pi]都没有 被牛牛接待，这名选手就会向主办方投诉，从而导致牛牛丢掉这份宝贵的志愿者 工作。接待完所有选手的那一刻，牛牛的工作就完成了。
在时刻0，牛牛站在门口（距离门口0米）， 开心度为0。现在牛牛想知道， 不被选 手投诉的前提下，在工作完成的那个时刻，开心度最多可以是多少？（开心度可 以为负）。
输入
第一行 2个整数n, L，以空格相隔，含义如题面所述。
第二行 4个整数x00, x01, x10, x11，以空格相隔，含义如题面所述。
接下来n行， 每行 3个整数ti, pi, fi， 以空格相隔， 代表第i个选手的到达时间， 耐 心值，友善值。
输出
一行， 一个整数表示工作完成的那一刻牛牛开心度的最大值。
样例输入 复制
2 3
2 1 3 3
5 5 5
15 8 1
样例输出 复制
39提示
【样例 1 输入】
2 3
2 1 3 3
5 5 5
15 8 1
【样例 1 输出】
39
【样例 1 说明】
最优的策略如下：
在时间[0,5]，牛牛站在门口，开心度每秒降低2 ，一共降低了10，此时开心度 为−10。
在时刻5，牛牛接待了第一位选手，他的开心度上升了25，此时开心度为15。
在时间[5,8]，牛牛从门口向沙发走去，开心度每秒下降1 ，一共下降3，此时开 心度为12。
在时刻8到达沙发。
在时间[8,20]，牛牛躺在沙发上摸鱼，开心度每秒上升3 ，一共上升了36，此时 开心度为48。
在时间[20,23]，牛牛从沙发向门口走去，开心度每秒降低3 ，一共下降9，此时 开心度为39。
在时刻23，牛牛到达门口并接待第二位选手，开心度增加0。此时接待完所有 选手，该时刻开心度为39。
【样例 2 输入】
1 490000
1 1 1 100
1 999999 1
【样例 2 输出】
1020000
【数据范围】
1 ≤ x00, x01, x10, x10, fi ≤ 200, x01 + x10 ≥ 2x00 1 ≤ n ≤ 10^5, 1 ≤ L, ti, pi ≤ 10^9
对于前 10%的数据，满足1 ≤ n, L, ti, pi ≤ 15。
对于前 30%的数据，满足1 ≤ n, L, ti, pi ≤ 100 。 对于前 50%的数据，满足1 ≤ n, L, ti, pi ≤ 1000。
对于前 70%的数据，满足1 ≤ n ≤ 1000,1 ≤ L, ti, pi ≤ 10^9 。 对于 100%的数据，满足1 ≤ n ≤ 10^5, 1 ≤ L, ti, pi ≤ 10^9 。