题目描述

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

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

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

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

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

输入格式

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

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

题目大意

一共有 $N$ 个任务和 $M$ 天，一天只能做一个任务，任务只能做一次，任务当天做完。做完任务后可以在做完后的第 $A_i$ 天拿到 $B_i$ 的工资，问 $M$ 天内最多可以拿到多少工资？

3 4
4 3
4 1
2 2

5

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

10

1 1
2 1

0

提示

制約

• 入力は全て整数である。
• $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$

Sample Explanation 1

以下のように日雇いアルバイトを請けて働くと、報酬の合計は $5$ となり、このときが最大です。 - 今日、$1$ 件目の日雇いアルバイトを請けて働き、今日から $4$ 日後に報酬 $3$ を得ます。 - 明日(今日から $1$ 日後)、$3$ 件目の日雇いアルバイトを請けて働き、今日から $1+2\ =\ 3$ 日後に報酬 $2$ を得ます。