006 - 宝集め

問題

あなたは旅をして、宝石を集めています。
あなたが持っている袋は大きさに限りがあるため、$M$個までしか宝石を入れることが出来ません。
今から起こる$Q$個のイベントに対処してください。
イベントは2種類あり、内容は以下の通りです。
・イベント1
価値が$A$の宝石を見つける。袋に宝石が入りきるなら宝石を入れ、入りきらないのなら袋の中の宝石か見つけた宝石のうち1つを選んで捨て、それ以外の宝石を袋に入れる。
・イベント2
今袋の中にある宝石の価値の総和(合計)を答える。
なるべく価値の高い宝石を集めるように行動した時、イベント2で答える値を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$M$ $Q$
$Event_1$
$Event_2$
...
$Event_Q$

1行目に整数$M,Q$が与えられる。 2行目から$Q$行にかけてイベントの内容が与えられる。
イベントの内容は以下の形式で与えられる。
・イベント1

$1$ $A$

・イベント2

$2$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq M,Q,A \leq 2×10^5$
• 入力はすべて整数
• イベント2は必ず1回以上起こる。

入出力例

入力例1

2 5
1 3
1 4
2
1 5
2

出力例1

7
9

あなたはまず、価値3,4の宝石をそれぞれ見つけます。袋には2個までの宝石が入るので、これを入れて、7と出力します。
その後、価値5の宝石を見つけますが、袋には3個は入りきらないので、価値3の宝石を捨て、9と出力します。

入力例2

3 10
2
2
1 31585
1 26721
1 26733
1 4806
2
1 27499
1 19001
2

出力例2

0
0
85039
85817

イベント2の時点で、袋に入っている宝石の個数が0個かもしれません。

入力例3

4 20
1 22551
1 29447
2
1 1371
2
1 12461
1 31338
1 12442
1 21973
1 19715
1 22811
1 932
1 26745
1 6233
1 4425
1 736
1 1506
1 27103
1 4281
2

出力例3

51998
53369
114633

ここにそのようなケースを載せることはできませんが、答えがint型に収まらない場合もあります。