Oinng的简单背包（hard）

    新的一周，星穹铁道模拟宇宙积分奖励更新了。

    Oinng想尽快拿到更多的积分，于是在早八高数课打开了平板。

    现在一共有 N 个世界，Oinng一共有 M 时间来打模拟宇宙。

    已知通关第 i 个世界需要 w_i 时间，可以获得 v_i 积分。

    但是由于各种不可控原因，模拟宇宙会发生 Q 次修改，每次会修改其中一个世界的通关时间和积分奖励为 W 和 V。（每次修改独立, 互不影响）

    由于课堂时间有限(bushi，Oinng想要知道每次修改后，他在 M 时间内最多可以获得多少积分。

    单组输入

    第一行输入三个整数N, M, Q（1 ≤ N, M, Q ≤ 2000）表示有 N 个宇宙，有 M 时间， 有 Q 次修改。

    接下来 N 行，每行输入两个整数 v_i，w_i（0 < v_i ≤ 10⁶, 1 ≤ w_i ≤ M）表示打第 i 个世界获得的积分和需要的时间。

    接下来 Q 行，每行输入三个整数 x, V, W (1 <= x <= N, 0 < V <= 10⁶ , 1 <= W <= M)  表示修改第 x 个世界，使其获得积分为 V，通关时间为 W。

    输出 Q 行，每行一个整数。

    第 i 行的整数表示在第 i 次修改后，Oinng最多可以获得多少积分。

4 100 4
100 100
99 10
1 2
5 5
1 1000 10
2 1 100
3 11 90
4 5 5

1105
100
110
105
—————————————————————————————————————————————————————————————————————————————————————————————
Note:
第一行：修改第一宇宙为1000 10，此时最优方案是打第一二三四宇宙，花费27时间，获得1105积分。
第二行：修改第二宇宙为1 100，此时最优方案是打第一宇宙，花费100时间，获得100积分。
第三行：修改第三宇宙为11 90，此时最优方案是打第二三宇宙，花费100时间，获得110积分。
第四行：修改第四宇宙为5 5, 此时最优方案是打第二三四宇宙，花费17时间，获得105积分。