题目背景

译自 CCC 2025 Senior T3。本题满分为 $15$。

题目描述

有 $n$ 支笔，$m$ 种颜色。第 $i$ 支笔的颜色为 $c_i$，美丽度为 $p_i$。

现在要用这些笔来画画。画会用到 $m$ 种颜色，所以要从每种颜色的笔中各选出一支，画的美丽度就是选出的笔的美丽度之和。

在下笔前，你可以选择至多一支笔，将这支笔的颜色改成 $[1,m]$ 中的任意一种。画完后，这支笔的颜色将恢复为原本的颜色。

有 $q$ 次操作：

• $\texttt{1}$ $i$ $x$：令 $c_i\gets x$。
• $\texttt{2}$ $i$ $y$：令 $p_i\gets y$。

对于 $i=1,2,\ldots,q+1$，求出：在完成前 $(i-1)$ 次操作后，用这些笔画出画的美丽度最大值。

再次强调，画完一幅画后，这支笔的颜色将恢复为原本的颜色。

输入格式

第一行，三个非负整数 $n,m,q$。

接下来 $n$ 行，每行两个正整数 $c_i,p_i$。

接下来 $q$ 行，每行三个正整数，描述一个操作。

数据保证，在任意时刻，每种颜色都至少有一支笔。

输出格式

输出 $(q+1)$ 行，第 $i$ 行的正整数表示完成前 $(i-1)$ 次操作后，用这些笔画出画的美丽度最大值。

6 3 0
1 6
2 9
3 4
2 7
3 9
1 3

25

3 2 2
1 20
2 30
1 10
1 3 2
2 3 25

50
50
55

提示

样例解释

• 样例 $1$ 解释：

起初，有三种颜色的笔：

• 颜色 $1$ 的笔的美丽度为 $3,6$。
• 颜色 $2$ 的笔的美丽度为 $7,9$。
• 颜色 $3$ 的笔的美丽度为 $4,9$。

如果不改变笔的颜色，画的最大美丽度为 $6+9+9=24$。

然而，将第 $4$ 支笔的颜色从 $2$ 改成 $1$ 可以获得 $7+9+9=25$ 的美丽度，这也是最优方案。

• 样例 $2$ 解释：

在第一次修改前和第二次修改前，选择第 $1,2$ 支笔是最优的。

在第二次修改后，选择第 $2,3$ 支笔是最优的。

子任务

对于 $100\%$ 的数据，保证：

• $1\le m\le n\le 2\times 10^5$；
• $0\le q\le 2\times 10^5$；
• $1\le c_i,x\le m$；
• $1\le p_i,y\le 10^9$；
• $1\le i\le n$；
• 在任意时刻，每种颜色都至少有一支笔。

---

子任务 $0$ 为样例。

$\text{Subtask}$	$n\le$	$m$	$q\le$	特殊性质	得分
$1$	$2\times 10^5$	$\le 2\times 10^5$	$0$	/	$5$
$2$		$=1$	$\le 2\times 10^5$		$2$
$3$		$=2$
$4$		$\le 10$
$5$		$\le 2\times 10^5$		$\text{A}$
$6$				/

• 特殊性质 $\text{A}$：数据保证在任意时刻，$n$ 支笔的美丽度都是两两不同的。