2014 Canadian Computing Competition, Stage 2

Day 2, Problem 1: Where's That Fuel?

The heroic Team Star Fox is on a mission to collect as much fuel as possible from various planets across the Lylat System. There are N (1 ≤ N ≤ 10⁵) planets, and the i-th one contains A_i fuel cells - but travelling there from any other planet uses up B_i fuel cells (1 ≤ A_i, B_i ≤ 10⁴). Unfortunately, fuel cells are not a sustainable resource, so if a planet is visited for a second time, there will be no new fuel to collect.

Team Star Fox starts on planet P (1 ≤ P ≤ N) - as such, they may collect its fuel cells immediately. They may then travel to as many different planets as they'd like to, in any order, as long as they have sufficient fuel to spend on each flight (that is, their fuel cell count remains non-negative). Finally, they may choose to stop at any point (possibly even before leaving planet P), with the goal of maximizing the number of fuel cells they end up with. If this can be done in multiple ways, they'd like to maximize the number of different planets they visit as a secondary objective. Can you help our heroes?

Input

The first line contains two integers: N (1 ≤ N ≤ 10⁵), followed by a space, followed by P (1 ≤ P ≤ N), which represents the number of planets followed by the starting planet number. The next N lines contain A_i, followed by a space, followed by B_i (1 ≤ A_i, B_i ≤ 10⁴).

You can assume that for test cases worth 20% of the marks, N ≤ 10.

Output

The output consists of two lines, with each line containing one positive integer. The first line contains the largest number of fuel cells that Team Star Fox can possess once they decide to stop. The second line contains the largest number of planets that Team Star Fox can visit, such that they still end up with this maximal number of fuel cells.

Sample Input

5 2
12 12
10 100
8 3
4 5
25 15

Sample Output

25
4

Explanation

Team Star Fox starts on planet 2, on which they collect 10 fuel cells to start off. They should proceed by travelling to planet 3, costing them 3 fuel cells but then increasing their fuel cell count to 15. Next, they can fly to planet 1, lowering their fuel cell count to 3 but then promptly restoring it to 15. Finally, they have just enough fuel to reach planet 5, at which point they can collect its fuel cells to end up with 25. They should then choose to stop without ever visiting planet 4.

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 17, 2014
Author: SourSpinach

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

Comments (Search)