Canadian Computing Competition: 2014 Stage 2, Day 2, Problem 1

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 \le N \le 10^5)~ 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 \le A_i, B_i \le 10^4)~. 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 \le P \le 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 Specification

The first line contains two integers: ~N~ ~(1 \le N \le 10^5)~, followed by a space, followed by ~P~ ~(1 \le P \le 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 \le A_i, B_i \le 10^4)~.

You can assume that for test cases worth about 20% of the marks, ~N \le 10~.

Output Specification

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

Output for Sample Input

25
4

Explanation of Output for Sample Input

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 capacity 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~.