L - Sushi-Go-Round Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

高橋君と青木君が回転寿司屋に来ました。最初、高橋君と青木君の満足度はともに 0 です。

これから N 皿の寿司が順に流れ、各皿を高橋君と青木君のどちらかが必ず取ります。
i 番目の皿を高橋君が取ると高橋君の満足度は A_i 増え、青木君が取ると青木君の満足度は B_i 増えます。皿を取らなかった方の満足度は変化しません。

どの瞬間にも高橋君と青木君の満足度の差の絶対値が M 以下であるように N 皿を順に分けるとき、最終的な高橋君の満足度の最大値を求めてください。

どの瞬間にも高橋君と青木君の満足度の差の絶対値が M 以下であるように N 皿を順に分けることができないときはそのことを報告してください。

制約

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

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

どの瞬間にも高橋君と青木君の満足度の差が M 以下であるように N 皿を順に分けるとき、最終的な高橋君の満足度の最大値を出力せよ。

どの瞬間にも高橋君と青木君の満足度の差が M 以下であるように N 皿を順に分けることができないとき、かわりに -1 を出力せよ。

入力例 1

5 7
3 1
4 1
5 9
2 6
5 3

出力例 1

14

次のように分けることができます。

  • 1 番目の皿を高橋君が取る。高橋君の満足度は 3、青木君の満足度は 0 となる。
  • 2 番目の皿を高橋君が取る。高橋君の満足度は 7、青木君の満足度は 0 となる。
  • 3 番目の皿を青木君が取る。高橋君の満足度は 7、青木君の満足度は 9 となる。
  • 4 番目の皿を高橋君が取る。高橋君の満足度は 9、青木君の満足度は 9 となる。
  • 5 番目の皿を高橋君が取る。高橋君の満足度は 14、青木君の満足度は 9 となる。

どの瞬間にも満足度の差の絶対値が 7 以下になるようにして高橋君の満足度を 15 以上にすることはできないため、これが最大です。

入力例 2

5 3
3 1
4 1
5 9
2 6
5 3

出力例 2

10

次のように分けることができます。

  • 1 番目の皿を青木君が取る。高橋君の満足度は 0、青木君の満足度は 1 となる。
  • 2 番目の皿を青木君が取る。高橋君の満足度は 0、青木君の満足度は 2 となる。
  • 3 番目の皿を高橋君が取る。高橋君の満足度は 5、青木君の満足度は 2 となる。
  • 4 番目の皿を青木君が取る。高橋君の満足度は 5、青木君の満足度は 8 となる。
  • 5 番目の皿を高橋君が取る。高橋君の満足度は 10、青木君の満足度は 8 となる。

入力例 3

5 2
3 1
4 1
5 9
2 6
5 3

出力例 3

-1

どのように分けても、満足度の差の絶対値が 2 より大きくなる瞬間が発生してしまいます。

入力例 4

20 70
22 75
26 45
72 81
47 29
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80

出力例 4

496

Problem Statement

Takahashi and Aoki came to a conveyor belt sushi restaurant. Initially, each person's happiness is 0.

N dishes of sushi will approach them in order. Each dish is always taken by Takahashi or Aoki.
If Takahahsi takes the i-th dish, Takahashi's happiness increases by A_i; if Aoki takes it, Aoki's happiness increases by B_i. Here, the other person's happiness does not change.

They will distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment. Find the maximum possible final happiness of Takahashi.

If they cannot distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment, report that fact.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 100
  • 1 \leq A_i,B_i \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the maximum final happiness of Takahashi when they distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment.

Print -1 instead if they cannot distribute the N dishes in order so that the absolute difference of their happinesses does not exceed M at any moment.

Sample Input 1

5 7
3 1
4 1
5 9
2 6
5 3

Sample Output 1

14

They can distribute the dishes as follows:

  • Takahashi takes the 1-st dish. Takahashi's happiness is now 3, and Aoki's is 0.
  • Takahashi takes the 2-nd dish. Takahashi's happiness is now 7, and Aoki's is 0.
  • Aoki takes the 3-rd dish. Takahashi's happiness is now 7, and Aoki's is 9.
  • Takahashi takes the 4-th dish. Takahashi's happiness is now 9, and Aoki's is 9.
  • Takahashi takes the 5-th dish. Takahashi's happiness is now 14, and Aoki's is 9.

This yields the maximum value, because one cannot make the final happiness of Takahashi 15 or greater while keeping the absolute difference of their happinesses not greater than 7.

Sample Input 2

5 3
3 1
4 1
5 9
2 6
5 3

Sample Output 2

10

They can distribute the dishes as follows:

  • Aoki takes the 1-st dish. Takahashi's happiness is now 0, and Aoki's is 1.
  • Aoki takes the 2-nd dish. Takahashi's happiness is now 0, and Aoki's is 2.
  • Takahashi takes the 3-rd dish. Takahashi's happiness is now 5, and Aoki's is 2.
  • Aoki takes the 4-th dish. Takahashi's happiness is now 5, and Aoki's is 8.
  • Takahashi takes the 5-th dish. Takahashi's happiness is now 10, and Aoki's is 8.

Sample Input 3

5 2
3 1
4 1
5 9
2 6
5 3

Sample Output 3

-1

Any distribution will make the absolute difference of the happinesses greater than 2 at some moment.

Sample Input 4

20 70
22 75
26 45
72 81
47 29
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80

Sample Output 4

496