B - 山を下るハイカー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は現在、標高 X メートルの地点にいます。これから山を下りながら、途中にある N 箇所の休憩スポットの中からいくつかを選んで立ち寄ることができます。

i 番目の休憩スポットは標高 A_i メートルの地点にあり、立ち寄ると景観スコア B_i を得ることができます。景観スコアは負の値の場合もあります（例えば、悪天候で不快な思いをする場合などです）。

高橋君は N 箇所の休憩スポットの中から 0 箇所以上を選んで立ち寄ります。各スポットには高々 1 回しか立ち寄ることができません。立ち寄るスポットを選ぶ際には、以下の条件をすべて満たす必要があります。

  • 立ち寄るスポットの標高は、すべて X より厳密に低くなければならない。すなわち、立ち寄る各スポットの標高 A_i は A_i < X を満たす。
  • 立ち寄るスポットを訪問する順に並べたとき、標高が厳密に減少していなければならない。すなわち、あるスポットに立ち寄った後に次に立ち寄るスポットの標高は、直前に立ち寄ったスポットの標高よりも厳密に低くなければならない。

なお、条件を満たす範囲であれば、N 箇所のスポットのうちどれを選んでも、またどの順番で訪問しても構いません。

立ち寄ったスポットの景観スコアの合計が、高橋君の得る景観スコアです。どのスポットにも立ち寄らない場合、景観スコアの合計は 0 とします。

高橋君が得られる景観スコアの合計の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq X \leq 10^9
  • 1 \leq A_i \leq 10^9
  • -10^9 \leq B_i \leq 10^9
  • A_i はすべて異なる。
  • 入力はすべて整数である。

入力

N X
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、休憩スポットの個数を表す整数 N と、高橋君の現在の標高を表す整数 X が、スペース区切りで与えられる。
  • 2 行目から N 行では、各休憩スポットの情報が与えられる。
  • 1 + i 行目では、 i 番目の休憩スポットの標高 A_i と、そのスポットの景観スコア B_i が、スペース区切りで与えられる。

出力

高橋君が得られる景観スコアの合計の最大値を 1 行で出力せよ。

入力例 1

4 100
80 5
50 3
120 -1
30 -2

出力例 1

8

入力例 2

3 50
30 -5
20 -3
60 10

出力例 2

0

入力例 3

8 500
450 10
300 -5
100 20
600 100
200 15
350 -8
50 7
250 3

出力例 3

55

入力例 4

15 1000
900 -100
800 50
700 30
600 -20
500 40
400 -10
300 60
200 -5
100 25
1000 999
1100 500
50 -1000
150 35
250 -15
850 70

出力例 4

310

入力例 5

1 1
1 1000000000

出力例 5

0

Score : 300 pts

Problem Statement

Takahashi is currently at an elevation of X meters. He is going to descend the mountain and can choose to visit some of the N rest spots along the way.

The i-th rest spot is located at an elevation of A_i meters, and visiting it gives him a scenic score of B_i. The scenic score can be negative (for example, due to bad weather causing an unpleasant experience).

Takahashi selects 0 or more of the N rest spots to visit. He can visit each spot at most once. When choosing which spots to visit, all of the following conditions must be satisfied:

  • The elevation of every spot he visits must be strictly less than X. That is, the elevation A_i of each visited spot satisfies A_i < X.
  • When the visited spots are listed in the order they are visited, the elevations must be strictly decreasing. That is, the elevation of each subsequently visited spot must be strictly lower than the elevation of the previously visited spot.

As long as the conditions are satisfied, he may choose any of the N spots to visit and in any order.

The total scenic score Takahashi obtains is the sum of the scenic scores of the spots he visits. If he does not visit any spot, the total scenic score is 0.

Find the maximum total scenic score Takahashi can obtain.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq X \leq 10^9
  • 1 \leq A_i \leq 10^9
  • -10^9 \leq B_i \leq 10^9
  • All A_i are distinct.
  • All input values are integers.

Input

N X
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of rest spots and an integer X representing Takahashi's current elevation, separated by a space.
  • The following N lines contain the information for each rest spot.
  • The (1 + i)-th line contains the elevation A_i of the i-th rest spot and its scenic score B_i, separated by a space.

Output

Print the maximum total scenic score Takahashi can obtain, on a single line.

Sample Input 1

4 100
80 5
50 3
120 -1
30 -2

Sample Output 1

8

Sample Input 2

3 50
30 -5
20 -3
60 10

Sample Output 2

0

Sample Input 3

8 500
450 10
300 -5
100 20
600 100
200 15
350 -8
50 7
250 3

Sample Output 3

55

Sample Input 4

15 1000
900 -100
800 50
700 30
600 -20
500 40
400 -10
300 60
200 -5
100 25
1000 999
1100 500
50 -1000
150 35
250 -15
850 70

Sample Output 4

310

Sample Input 5

1 1
1 1000000000

Sample Output 5

0