配点 : $400$ 点

問題文

$N$ 件の日雇いアルバイトがあり、$i$ 件目の日雇いアルバイトを請けて働くと、その $A_i$ 日後に報酬 $B_i$ が得られます。

あなたは、これらの中から $1$ 日に $1$ 件まで選んで請け、働くことができます。

ただし、請けたことのある日雇いアルバイトは選べません。

今日から $M$ 日後まで($M$ 日後を含む)に得られる報酬の合計の最大値を求めてください。

なお、日雇いアルバイトは今日から請けて働くことができます。

制約

• 入力は全て整数である。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq 10^5$
• $1 \leq B_i \leq 10^4$

入力

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

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

出力

$M$ 日後までに得られる報酬の合計の最大値を出力せよ。

3 4
4 3
4 1
2 2

5

以下のように日雇いアルバイトを請けて働くと、報酬の合計は $5$ となり、このときが最大です。

• 今日、$1$ 件目の日雇いアルバイトを請けて働き、今日から $4$ 日後に報酬 $3$ を得ます。
• 明日(今日から $1$ 日後)、$3$ 件目の日雇いアルバイトを請けて働き、今日から $1+2 = 3$ 日後に報酬 $2$ を得ます。

5 3
1 2
1 3
1 4
2 1
2 3

10

1 1
2 1

0