{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$.\u003c/p\u003e\u003cp\u003eGrammy, 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.\u003c/p\u003e\u003cp\u003eGrammy 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.\u003c/p\u003e\u003cp\u003eGrammy 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:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e1 x c v\u003c/span\u003e\" ($$$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. \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e2 s k\u003c/span\u003e\" ($$$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. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains only a single case.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eIn 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.\u003c/p\u003e\u003cp\u003eEach of the next $$$m$$$ lines describes an event in formats described in the statement above.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each event of the second type, print a single line containing an integer, the maximum total value of jewels that can be achieved.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6\n1 3\n2 4\n3 1\n2 2\n3 5\n2 1 0\n2 1 1\n2 1 2\n1 4 3 3\n2 3 1\n2 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n8\n12\n3\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}