34468번 - Pretty Pens 다국어

문제

You are taking an art class, and your current art assignment is very algorithmic.

You have $N$ pens, each of which has a single colour, represented by an integer from 1ドル$ to $M$. Initially, the colour of the $i$-th pen is given by C$_i$. In addition, your pens are pretty, with the $i$-th pen having a prettiness of $P_i$.

For your assignment, you need to create a picture using $M$ strokes, each from a pen of a different colour. The prettiness of your picture is the sum of the prettiness of the pens used to create the picture.

Your teacher has given you some room for artistic expression: before you create this pretty picture, you are allowed to change at most one pen to any other colour. After this picture is drawn, the pen will revert back to its original colour.

Your teacher will give you $\frac{1} {3}$ of the marks (5ドル$ of 15ドル$ total marks) for the art assignment based on creating the prettiest picture you can.

To push your creative limits, your teacher also has $Q$ more pictures for you to create, which compose the remaining $\frac{2}{3}$ of the marks (10ドル$ of 15ドル$ total marks) for your art assignment. Before each picture, there will be one of two possible changes to the set of pens available:

• 1ドル$ $i$ $c$ indicates that the colour of the $i$-th pen changes to $c$.
• 2ドル$ $i$ $p$ indicates that the prettiness of the $i$-th pen changes to $p$.

The changes are executed sequentially (so the first change modifies the initial setup, the second change modifies the result of applying the first change, and so on).

As in the first picture you created, you are allowed to change the colour of at most one pen before the picture is created. Note that if you do change the colour of one pen, it affects only the next picture you draw, and the pen will revert to its previous colour before the next change is applied (if any).

What is the prettiness of the prettiest $Q + 1$ pictures you can create?

입력

The first line of input contains three space-separated integers $N,ドル $M,ドル and $Q $(1ドル ≤ M ≤ N ≤ 200,円 000,ドル 0ドル ≤ Q ≤ 200,円 000$).

The next $N$ lines each contain two space-separated integers, $C_i $and $P_i$ (1ドル ≤ C_i ≤ M,ドル 1ドル ≤ P_i ≤ 10^9$), indicating the colour and prettiness of the $i$-th pen.

The next $Q$ lines each contain three space-separated integers, beginning with 1ドル$ or 2ドル$. If the first integer is 1ドル,ドル it is followed by two integers $i_j$ and $c_j$ (1ドル ≤ i_j ≤ N,ドル 1ドル ≤ c_j ≤ M$), representing a change of the colour of the i$_j$-th pen to $c_j$. If the first integer is 2ドル,ドル it is followed by two integers $i_j$ and $p_j$ (1ドル ≤ i_j ≤ N,ドル 1ドル ≤ p_j ≤ 10^9 $), representing a change of the prettiness of the $i_j$-th pen to $p_j$.

It is guaranteed that initially and after each change, there is at least one pen with each of the $M$ colours.

출력

The output is $Q + 1$ lines, with the $j$-th line containing one integer, the largest possible prettiness value obtainable after the first $j − 1$ changes have been performed.

제한

노트