Woburn Challenge 2016-17 Round 1 - Senior Division

Problem 3: Tricky's Treats

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 ≤ N ≤ 10⁵) other houses on the street, with the i-th one being P_i (1 ≤ P_i ≤ 10⁹) 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 ≤ C_i ≤ 10⁴) 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 ≤ M ≤ 43,200,000) 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 ≤ T ≤ 10⁴) 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 ≤ 10 and M ≤ 2000.
In test cases worth another 6/30 of the points, N ≤ 500 and M ≤ 2000.
In test cases worth another 6/30 of the points, N ≤ 1000.

Input Format

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..N).

Output Format

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 2nd house, collect its treats, walk to the 3rd 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 4th 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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Oct 16, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)