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
other houses on the street, with the
one being
metres away from his own house. No two houses
are at the same location. If Tricky visits the
house and scares
its residents with a fearsome dinosaur roar, he's sure to receive
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
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
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 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 of the points,
and
.
In test cases worth another of the points,
and
.
In test cases worth another of the points,
.
Input Specification
The first line of input consists of three space-separated integers ,
, and
.
lines follow, with the
of these lines consisting of two
space-separated integers
and
(for
).
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 house, collect its
treats, walk to the
house, collect its treats, and then walk back
home. This takes
milliseconds, and
yields a bounty of
treats. If the
house were
metre
closer to Tricky's house, then he would have just enough time to walk
straight to it, collect its
treats, and make it back home at
midnight.
Comments
1000 milliseconds * 1 meter per millisecond = 1000 metres per second. Is bro The Flash or something