#P18587. Quartz Collection

Quartz Collection

Quartz Collection

商店每天出售 nn 种水晶,每种恰有两块。第 ii 种的第一块售价 aia_i,第二块售价 bib_i。只有第一块已经售出,才能购买这一种的第二块。

Alice 和 Bob 每天都要各买每种水晶恰好一块,并按如下顺序购买:

  1. Alice 先买一块。
  2. 此后 Bob、Alice 轮流各买两块。每块购买后,库存立即变化,下一块可以根据新库存选择。
  3. 最后若只剩一块,由尚未买齐全部种类的人买走。

两人每次都只能购买自己当天尚未拥有的种类。他们都采取最优策略,使自己的总花费最少。

接下来的 mm 天,每天都会有一种水晶的两个价格发生永久修改。在每天开始购买前,库存恢复为每种两块;仅价格修改会延续到后面的日期。

请输出初始这一天以及每次修改之后,双方最优行动时 Alice 买齐所有种类的最小花费。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,第 ii 行两个整数 ai,bia_i,b_i,表示第 ii 种水晶第一块和第二块的价格。

接下来 mm 行,每行三个整数 t,x,yt,x,y,表示将第 tt 种水晶的价格永久改为 at=x,bt=ya_t=x,b_t=y。修改可以保持价格不变。

输出格式

输出 m+1m+1 行。第一行为初始价格下的答案,后面依次为每次修改后的答案。答案不取模。

数据范围

1≤n,m≤1051\le n,m\le10^5,1≤ai,bi,x,y≤1051\le a_i,b_i,x,y\le10^5,1≤t≤n1\le t\le n。输入只有一组数据。

样例输入

4 5
2 4
5 7
1 7
2 1
4 5 2
1 6 2
4 4 3
2 1 3
3 6 6

样例输出

13
14
15
14
10
13

样例说明

初始这一天的一种最优行动是:Alice 先买第3种的第一块;Bob 买第1、2种的第一块;Alice 买第1、2种的第二块;Bob 买第3种的第二块和第4种的第一块;Alice 买走第4种的第二块。Alice 共花 1+4+7+1=131+4+7+1=13。