Drawing with Pens

You are given n pens and m colors. The i^th pen has a color c_i and a beauty value p_i. You want to create a drawing using these pens. The drawing requires exactly one pen of each color from 1 to m, and the beauty of the drawing is the sum of the beauty values of the chosen pens.

Before drawing, you are allowed to choose at most one pen and temporarily change its color to any color in the range [1, m]. After the drawing is complete, the pen reverts to its original color.

In addition, there will be q operations. Each operation is one of the following types:

• 1 i x: change the color of pen i to x (i.e. set c_i = x).
• 2 i y: change the beauty value of pen i to y (i.e. set p_i = y).

Let the state i (for i = 1 to q+1) be the configuration after performing (i-1) operations (state 1 is the initial configuration before any operation). For each state, compute the maximum possible beauty of a drawing achievable by selecting one pen per color, while using the option to recolor at most one pen optimally if needed.

Important note:

• If a color is missing and there is no way to fix it (i.e. if there are at least 2 missing colors, or if trying to recolor a pen would leave its original color empty), then the drawing is impossible. In such cases, output -1.
• If no recoloring is needed, the beauty is simply the sum of the maximum beauty values over all colors.
• If recoloring is applied, you choose one pen from a color a (provided that its removal does not make color a empty) and recolor it to some other color b (which might be originally missing or whose best candidate is not optimal). The overall drawing beauty then becomes the sum for every color, where the contribution for color a becomes the second highest beauty value available in that color (since the chosen pen is removed), and the contribution for color b becomes the beauty value of the recolored pen if this is higher than the originally available candidate for color b.

For each state, output the maximum drawing beauty that can be achieved, or -1 if it is impossible.

The formulas used in the analysis are given in LaTeX format. For example, if no recoloring is applied, the drawing beauty is:

$S_0=\sum_{c=1}^m \max\{p_i: c_i=c\}$

If a pen from color a (with best value $B_a$ and second best $S_a$) is recolored to color b (with current best $B_b$), the modified drawing beauty becomes:

$S_0- (B_a - S_a) + (p_i - B_b)$

(Note that this change only applies if the pen being recolored is the unique candidate for its color then such a move is invalid.)

inputFormat

The first line contains three integers n, m and q --- the number of pens, the number of colors, and the number of operations, respectively.

The next n lines each contain two integers c_i and p_i, describing the initial color and beauty of the i^th pen.

The following q lines describe the operations. Each operation is in one of the following formats:

• 1 i x: change the color of pen i to x.
• 2 i y: change the beauty value of pen i to y.

It is guaranteed that 1 ≤ c_i ≤ m, and after each operation the parameters will be valid.

outputFormat

Output q+1 lines. The i^th line (for i = 1 to q+1) should contain a single integer, the maximum drawing beauty obtainable after performing i-1 operations. If it is impossible to create a drawing (i.e. there is more than one color missing or a necessary recoloring move is invalid), output -1 for that state.

sample

3 2 2
5  (for pen 1 color:1, beauty:5)
3  (for pen 2: color:1, beauty:3)
4  (for pen 3: color:2, beauty:4)
1 3 1
2 2 6

9
9
11

</p>