Woburn Challenge 2016-17 Round 1 - Senior Division

Oh boy! It's Tricky's favourite time of year, Halloween! He can't wait to put on his awesome dinosaur costume and take a walk around his neighbourhood. Of course, what he's looking forward to the most are the loads of treats his neighbours are sure to give him!

Tricky lives at one end of a long street. There are $N$ $(1\le N\le {10}^5)$ other houses on the street, with the $i^{th}$ one being $P_i$ $(1\le P_i\le {10}^9)$ metres away from his own house. No two houses are at the same location. If Tricky visits the $i^{th}$ house and scares its residents with a fearsome dinosaur roar, he's sure to receive $C_i$ $(1\le C_i\le {10}^4)$ treats from them. Of course, he can only visit each house at most once, though.

Tricky would love to get as many treats as possible, but one thing may stand in his way - time! He absolutely must be home no later than midnight (that's when the real monsters come out). Fortunately, he may be getting quite a head start on his trick-or-treating expedition - he'll be leaving home $M$ $(1\le M\le 43200000)$ milliseconds before midnight.

Despite his elaborate costume and the potential weight of many treats, Tricky can get around pretty quickly. He can walk down the street in either direction at a rate of 1 metre per millisecond. If he decides to stop at a house along the way to collect its treats, it'll take him $T$ $(1\le T\le {10}^4)$ milliseconds to do so before he can continue on his way.

Given that Tricky must be back in the safety of his house at the end of the street after no more than $M$ milliseconds of trick-or-treating, how many treats can he possibly end up with, and what's the probability of him developing long-lasting health issues as a result of the following excessive sugar consumption? (Just kidding, he'll be just fine!)

In test cases worth $3/30$ of the points, $N\le 10$ and $M\le 2000$.
In test cases worth another $6/30$ of the points, $N\le 500$ and $M\le 2000$.
In test cases worth another $6/30$ of the points, $N\le 1000$.

Input Specification

The first line of input consists of three space-separated integers $N$, $M$, and $T$.
$N$ lines follow, with the $i^{th}$ of these lines consisting of two space-separated integers $P_i$ and $C_i$ (for $i=1\dots N$).

Output Specification

Output one line consisting of a single integer - the maximum number of treats that you can receive while still returning home by midnight.

Sample Input

4 2000 500
123 4
400 20
100 5
751 999

Sample Output

25

Sample Explanation

One optimal strategy is for Tricky to walk to the $2^{nd}$ house, collect its treats, walk to the $3^{rd}$ house, collect its treats, and then walk back home. This takes $400+500+300+500+100=1800$ milliseconds, and yields a bounty of $20+5=25$ treats. If the $4^{th}$ house were $1$ metre closer to Tricky's house, then he would have just enough time to walk straight to it, collect its $999$ treats, and make it back home at midnight.