Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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 個を選んで入手するとき、得られる満足度の合計としてあり得る最大値を求めてください。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- T_i は 0,1,2 のいずれか
- 1 \leq X_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M T_1 X_1 T_2 X_2 \vdots T_N X_N
出力
答えを整数として出力せよ。
入力例 1
8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100
出力例 1
27
1, 2, 5, 7 個目の品物を入手し、7 個目の品物である缶切りを 5 個目の品物に対して使用すると、満足度 6 + 6 + 15 = 27 を得ます。
満足度が 28 以上になる品物の入手方法は存在しませんが、上記の例において 7 個目の品物のかわりに 6 個目の品物や 8 個目の品物を選んでも満足度 27 を得ることができます。
入力例 2
5 5 1 5 1 5 1 5 1 5 1 5
出力例 2
0
入力例 3
12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4
出力例 3
30
Score : 500 points
Problem Statement
There are N items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The i-th item is described by an integer pair (T_i, X_i) as follows:
- If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i.
- If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i.
- If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans.
Find the maximum total happiness that you get by obtaining M items out of N.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- T_i is 0, 1, or 2.
- 1 \leq X_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M T_1 X_1 T_2 X_2 \vdots T_N X_N
Output
Print the answer as an integer.
Sample Input 1
8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100
Sample Output 1
27
If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27.
There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above.
Sample Input 2
5 5 1 5 1 5 1 5 1 5 1 5
Sample Output 2
0
Sample Input 3
12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4
Sample Output 3
30