#P18587. Quartz Collection
Quartz Collection
Quartz Collection
商店每天出售 种水晶,每种恰有两块。第 种的第一块售价 ,第二块售价 。只有第一块已经售出,才能购买这一种的第二块。
Alice 和 Bob 每天都要各买每种水晶恰好一块,并按如下顺序购买:
- Alice 先买一块。
- 此后 Bob、Alice 轮流各买两块。每块购买后,库存立即变化,下一块可以根据新库存选择。
- 最后若只剩一块,由尚未买齐全部种类的人买走。
两人每次都只能购买自己当天尚未拥有的种类。他们都采取最优策略,使自己的总花费最少。
接下来的 天,每天都会有一种水晶的两个价格发生永久修改。在每天开始购买前,库存恢复为每种两块;仅价格修改会延续到后面的日期。
请输出初始这一天以及每次修改之后,双方最优行动时 Alice 买齐所有种类的最小花费。
输入格式
第一行两个整数 。
接下来 行,第 行两个整数 ,表示第 种水晶第一块和第二块的价格。
接下来 行,每行三个整数 ,表示将第 种水晶的价格永久改为 。修改可以保持价格不变。
输出格式
输出 行。第一行为初始价格下的答案,后面依次为每次修改后的答案。答案不取模。
数据范围
,,。输入只有一组数据。
样例输入
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 共花 。