AT_past202303_n ゴミ出し

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 $ .

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 $

Print the answer.

### Sample Explanation 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 Explanation 2 There is no $ X $ such that he can have at most $ C $ kilograms of garbage in the morning of day $ D $ . ### 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.