[CF436E] Cardboard Box

我们称一星通关的关卡为 A 类，二星通关的关卡为 B 类。

将关卡序列按照 $b_i$ 从小到大排序，显然在最优解中所有 B 类关卡一定排在所有未通关关卡之前。

也即我们选择一个分界点，将分界点之前划为 B 类关卡，分界点之后划为 A 类关卡，接着选择一些 A 类关卡改为不通关，选择一些 B 类关卡划入 A 类关卡。一定存在合适的分界点使得上述方案能够得出最优解。

于是我们对于每个可能的分界点，先计算出目前的总代价，然后衡量将分界点左侧的 B 类关卡降格为 A 类和分界点右侧的 A 类关卡改为不通关能够获得的收益，那么此分界点能够构造出的最小代价为总代价减去所有选择中收益前 $2p+q-w$ 大之和，其中 $p,q$ 分别为分界点左右侧关卡数。

那么我们从左到右枚举分界点，用堆维护所有选择的代价即可。