AT_abc312_f [ABC312F] Cans and Openers

[problemUrl]: https://atcoder.jp/contests/abc312/tasks/abc312_f $ N $ 個の品物があります。 これらはそれぞれ、缶切りが不要な缶・缶切りが必要な缶・缶切りのいずれかです。 $ i $ 個目の品物は、整数の組 $ (T_i,\ X_i) $ により次のように表されます。 - $ T_i\ =\ 0 $ ならば、$ i $ 個目の品物は缶切りが不要な缶で、入手すると満足度 $ X_i $ を得る。 - $ T_i\ =\ 1 $ ならば、$ i $ 個目の品物は缶切りが必要な缶で、入手した上で缶切りを使うと満足度 $ X_i $ を得る。 - $ T_i\ =\ 2 $ ならば、$ i $ 個目の品物は缶切りで、$ X_i $ 個までの缶に対して使用できる。 $ N $ 個の品物から $ M $ 個を選んで入手するとき、得られる満足度の合計としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ T_1 $ $ X_1 $ $ T_2 $ $ X_2 $ $ \vdots $ $ T_N $ $ X_N $

答えを整数として出力せよ。

### 制約 - $ 1\ \leq\ M\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ T_i $ は $ 0,1,2 $ のいずれか - $ 1\ \leq\ X_i\ \leq\ 10^9 $ - 入力される値はすべて整数 ### Sample Explanation 1 $ 1,\ 2,\ 5,\ 7 $ 個目の品物を入手し、$ 7 $ 個目の品物である缶切りを $ 5 $ 個目の品物に対して使用すると、満足度 $ 6\ +\ 6\ +\ 15\ =\ 27 $ を得ます。 満足度が $ 28 $ 以上になる品物の入手方法は存在しませんが、上記の例において $ 7 $ 個目の品物のかわりに $ 6 $ 個目の品物や $ 8 $ 個目の品物を選んでも満足度 $ 27 $ を得ることができます。