#P18045. Azalea Garden
Azalea Garden
Azalea Garden
有 个生物,第 个生物的攻击力和防御力分别为 。
一次战斗选择两个不同的、尚未被消灭的生物 。若 ,则消灭 ;否则没有变化。被消灭的生物不能参加本次战争的后续战斗。你可以安排任意有限次战斗,也可以不进行战斗。求最终存活生物数量的最小值。
随后发生 次修改。第 次修改将生物 的攻击力改为 ,防御力改为 。修改会保留,后面的修改在当前属性基础上进行。
你需要回答修改前以及每次修改后的最小存活数量。每次回答对应一场独立的假想战争,开始时所有 个生物都存活;此前答案中安排的战斗不会影响下一次回答。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 。
接下来 行,每行三个整数 。
输出格式
输出 行,依次为修改前、第一次修改后、第二次修改后……的答案。
数据范围
,,,所有攻击力和防御力均在 内。
样例 1
输入:
3 1
1 1
2 2
3 3
2 2 4
输出:
1
2