You are given two sequences of length $N$: $D=(D_1, D_2, \dots, D_N)$ and $P=(P_1, P_2, \dots, P_N)$.
Process $Q$ queries in the order they are given. Each query is given in the following format:

• c x y: Change $D_c$ to $x$ and $P_c$ to $y$. Then, solve the following problem and print the answer.

There are $N$ jobs numbered $1$ to $N$.
Starting from today (consider this as day $1$), you will choose and complete one job per day for $N$ days.
If you complete job $i$ on or before day $D_i$, you will receive a reward of $P_i$. (If you do not complete it by day $D_i$, you get nothing.)
Find the maximum total reward you can achieve by choosing the optimal order of completing the jobs.

The input is given from Standard Input in the following format. Here, $\mathrm{query}_i$ denotes the $i$-th query.

```
$N$ $Q$
$D_1$ $D_2$ $\dots$ $D_N$
$P_1$ $P_2$ $\dots$ $P_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
```

Each query is given in the following format.

```
$c$ $x$ $y$
```

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

-   $1 \leq N \leq 10^5$
-   $1 \leq Q \leq 10^5$
-   $1 \leq D_i \leq N$
-   $1 \leq P_i \leq 10^9$
-   $1 \leq c \leq N$
-   $1 \leq x \leq N$
-   $1 \leq y \leq 10^9$
-   All input values are integers.

10
13

The first query is as follows:

• Update $D_3$ to $1$ and $P_3$ to $4$. Now, $D = (1, 2, 1)$ and $P = (3, 6, 4)$.
• In the subproblem, one optimal procedure is to complete job $3$ on day $1$, job $2$ on day $2$, and job $1$ on day $3$. The total reward is $10$, so print $10$.

The second query is as follows:

• Update $D_2$ to $3$ and $P_2$ to $9$. Now, $D = (1, 3, 1)$ and $P = (3, 9, 4)$.
• In the subproblem, one optimal procedure is to complete job $3$ on day $1$, job $1$ on day $2$, and job $2$ on day $3$. The total reward is $13$, so print $13$.