AT_past202303_n ゴミ出し

次のような問題を考えます。 > 高橋君はある日 (これを $ 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ D $ $ d_1 $ $ a_1 $ $ d_2 $ $ a_2 $ $ \vdots $ $ d_N $ $ a_N $

答えを出力せよ。

### Sample Explanation 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 $ 円である。 ### Sample Explanation 2 どのような $ X $ に対しても $ D $ 日目の朝の時点でゴミを $ C $ kg 以下にすることはできません。 ### 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 $ - 入力される値は全て整数