406020: GYM102219 C I Don't Want To Pay For The Late Jar!

Nina from the IT support needs your help with another daily puzzle she faces. She is able to take her lunch break anytime she wants. But because of limited capacity, she only can take $$$S$$$ minutes based on the needs that day. Any extra minutes that she is late, she has to pay $$$RM 1$$$ to the late jar.

She prepared a list of her favorite restaurants and how long it would take for her to lunch in each restaurant based on experience, ($$$1$$$ ≤ $$$t_{i}$$$ ≤ $$$10^9$$$ ). She also assigned a value for each of the restaurants that shows how much extra she is willing to pay but still be happy, ($$$1$$$ ≤ $$$f_{i}$$$ ≤ $$$10^9$$$ ).

For example, if she needs $$$t_{x}$$$ minutes to dine in restaurant $$$x$$$ which she values $$$RM f_{x}$$$ . If $$$t_{x} ≤ S$$$ then she is fully happy and it is as if she saved $$$RM f_{x}$$$.

But if $$$t_{x} > S$$$ she would save $$$f_{x} - (t_{x} - S)$$$.

Please help her to find the restaurant that she would be happiest in and meanwhile save the most. Also, keep in mind she can choose exactly one restaurant to lunch each day.

The first line contains an integer – $$$D (1 ≤ D ≤ 10)$$$ – the number of days.

The second line contains two space-separated integers — $$$N (1 ≤ N ≤ 10^4 )$$$ and $$$S (1 ≤ S ≤ 10^9 )$$$ — the number of restaurants in Nina's list and her lunch break time for the day, correspondingly.

Each of the next $$$N$$$ lines contains two space-separated integers — $$$f_{i} (1 ≤ f_{i} ≤ 10^9 )$$$ and $$$t_{i}$$$ $$$(1 ≤ t_{i} ≤ 10^9 )$$$ — the characteristics of the $$$i_{th}$$$ restaurant.

In a single line print a single integer — the maximum money she is saving/her happiness by day.

2
2 5
3 3
4 5

1 5
1 7

Case #1: 4
Case #2: -1