N - Garbage Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

次のような問題を考えます。

高橋君はある日 (これを 1 日目とします) の朝の時点で X kg のゴミを持っています。ゴミは毎日夜に 1 kg 増えます。

ゴミを捨てることのできる機会は最大 N 回あります。i = 1, 2, \dots, N について、d_i 日目の朝の時点でゴミが a_i kg 以上あるならば、「1 円を払って a_i kg のゴミを捨てる」ことを 0 回または 1 回行うことができます。

高橋君は D 日目の朝の時点でゴミが C kg 以下になるようにしたいです。そのために払う金額としてありうる最小値を求めてください。

N, C, D, d_i, a_i は入力で与えられます。いま、X を非負整数の範囲で動かすことを考えます。

上記の問題において高橋君が D 日目の朝の時点でゴミを C kg 以下にすることができるような X に対する、問題の答えの最小値を求めてください。 ただし、どのような X に対しても D 日目の朝の時点でゴミを C kg 以下にすることができないならば、-1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq C \leq 10^9
  • 1 \leq d_1 \lt d_2 \lt \dots \lt d_N \lt D \leq 10^9
  • 1 \leq a_i \leq 10^9
  • 入力される値は全て整数

入力

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

N C D
d_1 a_1
d_2 a_2
\vdots
d_N a_N

出力

答えを出力せよ。

入力例 1

2 1 4
1 3
3 4

出力例 1

1

例えば、X = 2 のときの最適な行動の一例は次のようになります。

  • 1 日目の朝には X = 2 kg のゴミがある。d_1 = 1 だが、ゴミの重さが a_1 = 3 kg 未満なので、この日にゴミを捨てることはできない。
  • 1 日目の夜にゴミが 3 kg になる。
  • 2 日目の夜にゴミが 4 kg になる。
  • 3 日目の朝に 1 円を払いゴミを a_2 = 4 kg 捨てる。d_2 = 3 かつゴミの重さが a_2 = 4 kg 以上なので、この動作は可能である。この動作により、ゴミは 0 kg になる。
  • 3 日目の夜にゴミが 1 kg になる。
  • D = 4 日目の朝の時点でゴミは 1 kg であり、これは C kg 以下であるので条件を満たす。払った金額の合計は 1 円である。

入力例 2

3 10 100
10 20
20 20
30 20

出力例 2

-1

どのような X に対しても D 日目の朝の時点でゴミを C kg 以下にすることはできません。

入力例 3

4 4 10
2 3
4 5
6 1
8 4

出力例 3

2

Problem Statement

Consider the following problem.

Takahashi has X kilograms of garbage in the morning of some day (let us call it day 1). Each night, the amount of garbage increases by 1 kilogram.

There will be N days when he can take out the garbage. For i = 1, 2, \dots, N, if he has a_i or more kilograms of garbage in the morning of day d_i, he can take out a_i kilograms of garbage at the cost of 1 yen zero times or once.

Takahashi wants to have at most C kilograms of garbage in the morning of day D. Find the minimum amount of money needed to achieve this.

You are given N, C, D, d_i, a_i as the input. Now, consider X as a non-negative integer variable.

Find the minimum answer to the above problem for an X such that Takahashi can have at most C kilograms of garbage in the morning of day D. If there is no X such that he can have at most C kilograms of garbage in the morning of day D, print -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq C \leq 10^9
  • 1 \leq d_1 \lt d_2 \lt \dots \lt d_N \lt D \leq 10^9
  • 1 \leq a_i \leq 10^9
  • All values in the input are integers.

Input

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

N C D
d_1 a_1
d_2 a_2
\vdots
d_N a_N

Output

Print the answer.

Sample Input 1

2 1 4
1 3
3 4

Sample Output 1

1

For instance, below is an optimal sequence of actions for X = 2.

  • In the morning of day 1, he has X = 2 kilograms of garbage. We have d_1 = 1, but the amount of garbage is less than a_1 = 3 kilograms, so he cannot take out the garbage this day.
  • After the night of day 1, he has 3 kilograms of garbage.
  • After the night of day 2, he has 4 kilograms of garbage.
  • In the morning of day 3, he takes out a_2 = 4 kilograms of garbage at the cost of 1 yen, wihch is allowed because d_2 = 3 and he has not less than a_2 = 4 kilograms of garbage. Then, he has 0 kilograms of garbage.
  • After the night of day 3, he has 1 kilogram of garbage.
  • In the morning of day 4, he has 1 kilogram of garbage, which is not more than C kilograms and thus satisfies the objective. He paid 1 yen in total.

Sample Input 2

3 10 100
10 20
20 20
30 20

Sample Output 2

-1

There is no X such that he can have at most C kilograms of garbage in the morning of day D.

Sample Input 3

4 4 10
2 3
4 5
6 1
8 4

Sample Output 3

2