题意 ： Joisino 要去打 final。这场比赛中有 道题，Joisino 做第 道题花费的时间为 。
这场比赛中，选手的做题方式是选择自己想做的题来做（可以不做），并且一定能做出来。最后，选手的得分将以如下方式计算：
其中，二元组
需要满足的条件是：对于所有满足 的 ，第 题都做了。另外， 和 还需满足 。
主办方为参赛者提供了
种饮料，如果 Joisino 喝了第
种饮料，他做第 题时会兴奋，做第
题的时间将从 变成 （注意 不一定比 小）做其它题的时间不受影响。
一位参赛者只能带一种饮料进入考场。Joisino
想知道如果他喝下了每种饮料，他的最大得分。
，时限 。
先不考虑饮料。
不难发现，对于一个长为 的 AC
的题目的极大连续段，对答案的贡献为 。
记 表示考虑前 题能得到的最大收益， 为 的前缀和。
枚举最后一个极长连续段，有转移 ：
观察后面的
，已经是可以斜率优化的形式。
然后考虑如何处理饮料的单点修改。
记 表示只做题目 能得到的最大收益， 表示只做题目 能得到的最大收益， 表示必做题目 所能得到的最大收益。
对于询问 ，分做或不做题目
讨论，答案为
这俩货可以用前面的斜率优化
预处理。
用分治计算。
考虑包含
的极长连续段，对于连续段
，贡献为 ：
在 中处理
的所有子区间的贡献。
每次处理跨越
的区间对询问的贡献。
处理 的 。此时要求左端点 ，右端点 。
（对
的部分，翻转序列重做即可）
记
为此时区间右端点恰好在
的最优解。则有 ：
其中
仍然是可以斜率优化的形式。线性求出凸壳，再线性扫描即可。
计算完成后， 能向 贡献。
复杂度 。