408453: GYM103119 J Jewel Grab

The museum in Byteland has $$$n$$$ jewels on display. These jewels are arranged in a row, labeled by $$$1,2,\dots,n$$$ from left to right. Every precious stone is of one of $$$n$$$ distinct colors. The color of the jewel in the $$$i$$$-th leftmost place is $$$c_i$$$ while the value of it is $$$v_i$$$.

Grammy, the master thief, aims to steal some jewels from this museum. The museum is secured by some quite expensive alarms that unfortunately can not be hacked.

Grammy invented a device: a robotic hand that can grab some jewels without triggering any of the alarms. The hand will start at the $$$s$$$-th leftmost place, moving right one by one, taking all the jewels lying below the hand in the whole grab procedure (including the $$$s$$$-th jewel), and finish at any place Grammy likes. Grammy could easily take all the jewels using the device, but she knows that the more she takes, the harder it will be to get rid of them. She decided that the safest way is to take a set of jewels such that no two taken jewels share the same color. But soon she realized that in such a way she would miss many jewels, so she would like to control the device to skip no more than $$$k$$$ jewels in total, in such a way the skipped jewels will not be taken.

Grammy lost most of her money betting on programming contests. So she may do the grab many times. There will be $$$m$$$ events of two types, detailed below:

• "1 x c v" ($$$1\leq x\leq n$$$, $$$1\leq c\leq n$$$, $$$1\leq v\leq 10^9$$$): The museum replaces the jewel at the $$$x$$$-th leftmost place with a jewel whose color and value are $$$c$$$ and $$$v$$$ respectively.
• "2 s k" ($$$1\leq s\leq n$$$, $$$0\leq k\leq 10$$$): Grammy plans to do a new grab. She will control the hand to start at the $$$s$$$-th leftmost place, and will skip no more than $$$k$$$ jewels. Please write a program to compute the maximum total value of jewels she can take in this grab. Note that the museum will always put backup jewels to all the stolen places before the next event.

The input contains only a single case.

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 200\,000$$$), denoting the number of jewels and the number of events.

In the next $$$n$$$ lines, the $$$i$$$-th line $$$(1 \le i \le n)$$$ contains two integers $$$c_i$$$ and $$$v_i$$$ ($$$1\le c_i\leq n$$$, $$$1\leq v_i\leq 10^9$$$), describing the $$$i$$$-th jewel.

Each of the next $$$m$$$ lines describes an event in formats described in the statement above.

For each event of the second type, print a single line containing an integer, the maximum total value of jewels that can be achieved.

5 6
1 3
2 4
3 1
2 2
3 5
2 1 0
2 1 1
2 1 2
1 4 3 3
2 3 1
2 2 2

8
8
12
3
9