$\color{deeppink}夏树$
题目描述
小 T 在玩黄金矿工。
为了简化问题，我们假设矿工位于数轴原点，初始时有 $n$ 块金子，且每块金子都位于数轴的正半轴上。第 $i$ 块金子的坐标为 $x_i$，价值为 $v_i$。保证序列 $x_i$ 严格递增。获得第 $i$ 块金子所需的时间为 $x_i\cdot v_i$。注意：与原版游戏不同，矿工可以花 $x_i\cdot v_i$ 的时间直接获得某块金子，而不需要把它前面的金子先清理掉。
小 T 想知道在时限内能获得的金子价值之和最大是多少。但关卡有很多，每次通关后，金子以及时限会发生一些变化。具体来说，共有 $m$ 次操作，操作有以下两种。
删除第 $y$ 块金子，保证该金子之前没被删除过。
询问在有 $k$ 个单位时间时，获得金子的价值之和最大是多少。注意：每块金子每次询问只能获得一次，且询问之间独立。也就是说，这次获得的金子在之后的询问中依然会出现。
你能帮小 T 在每个关卡都获得理论最高的价值吗？
输入格式
从文件 natsuki.in 中读入数据。
第一行三个整数 $n,m,k_{\max}$，分别表示初始金子数，操作数和时限的上界。
第二行到第 $n+1$ 行，每行两个正整数 $x_i,v_i$，表示第 $i$ 块金子的位置和价值。
第 $n+2$ 行到第 $n+m+1$ 行，每行两个正整数，形如 1 y 或 2 k，表示一次操作。
输出格式
输出到文件 natsuki.out 中。
对于每个询问操作，输出一行一个整数表示答案。
样例 1
样例 1 输入
3 8 50
3 3
4 2
6 4
2 25
2 8
2 7
2 12
1 2
2 25
1 3
2 40样例 1 输出
5
2
0
3
4
3样例 1 解释
对于第 $1$ 个询问，最佳方案是获得第 $1$ 块金子和第 $2$ 块金子，总用时为 $3\cdot 3+4\cdot 2=17 \leq 25$，总价值为 $3+2=5$。
对于第 $2$ 个询问，最佳方案是获得第 $2$ 块金子，总用时为 $8$，总价值为 $2$。
对于第 $3$ 个询问，最佳方案是什么也不做，总用时为 $0$，总价值为 $0$。
对于第 $4$ 个询问，最佳方案是获得第 $1$ 块金子，总用时为 $9$，总价值为 $3$。
对于第 $5$ 个询问，由于第 $2$ 块金子已被删除，最佳方案是获得第 $3$ 块金子，总用时为 $24$，总价值为 $4$。
对于第 $6$ 个询问，由于第 $2$ 块金子和第 $3$ 块金子均已被删除，最佳方案是获得第 $1$ 块金子，总用时为 $9$，总价值为 $3$。
这组样例满足子任务 $1,3,4,5$ 的限制。
样例 2
样例 2 输入
见选手目录中的 natsuki/natsuki2.in样例 2 输出
见选手目录中的 natsuki/natsuki2.in这组样例满足子任务 $1,3,4,5$ 的限制。
样例 3
样例 3 输入
见选手目录中的 natsuki/natsuki3.in样例 3 输出
见选手目录中的 natsuki/natsuki3.in这组样例满足子任务 $2,5$ 的限制。
样例 4
样例 4 输入
见选手目录中的 natsuki/natsuki4.in样例 4 输出
见选手目录中的 natsuki/natsuki4.out这组样例满足子任务 $3,5$ 的限制。
样例 5
样例 5 输入
见选手目录中的 natsuki/natsuki5.in样例 5 输出
见选手目录中的 natsuki/natsuki5.out这组样例满足子任务 $4,5$ 的限制。
样例 6
样例 6 输入
见选手目录中的 natsuki/natsuki6.in样例 6 输出
见选手目录中的 natsuki/natsuki6.out这组样例满足子任务 $5$ 的限制。
数据范围
对于所有数据，$1\leq n\leq k_{\max}\leq 2\times 10^6$，$1\leq x_i\cdot v_i\leq k_{\max}$，$1\leq x_1
子任务 $1$（$22$ 分）：$n, k_{\max}\leq 5000$。
子任务 $2$（$26$ 分）：$m=1$。
子任务 $3$（$15$ 分）：$n\leq 5000$。
子任务 $4$（$21$ 分）：$n, k_{\max}\leq 3\times 10^5$。
子任务 $5$（$16$ 分）：无特殊限制。