Problem Statement

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.

Constraints

• $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.

Input

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

Output

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