[Coci2012]RASPORED

时间限制:20s      空间限制:128MB

题目描述

有n个订单,第i个订单需要你花费Ti的时间完成。若第i个订单在时刻t完成则
你的收益等于Li-t。总收益是各个订单收益的和。你可以自由地安排订单的完成顺
序。订单会发生m次变化。每j次变化是将第Vj个订单的内容更新为Lj’和Tj’。现
在要求你快速计算出最初的和每次变化后你的最大收益。


输入格式


输出格式


样例输入

4 2 
3 2 
0 3 
4 3 
4 1 
3 0 4 
1 4 5 
 
 
 

样例输出

 
-8 
-13 
-18 

提示

n, m <= 200,000.
Ti, Li <= 10,0000.


题目来源

没有写明来源