P7700 [CCC 2014] Fuel Collection

The brave Fox Star Squad is on a mission. Their task is to collect as much fuel as possible from different planets in the Layla galaxy. There are $n$ planets in the Layla galaxy. Planet $i$ contains $a_i$ units of fuel, but traveling to that planet from any planet costs $b_i$ units of fuel. Unfortunately, fuel is not a renewable resource, so if you visit a planet a second time, you will not collect any new fuel there. The Fox Star Squad starts on planet $P$, so they can immediately collect the fuel on that planet, and then they can begin the mission. As long as they have enough fuel (that is, after completing a flight, their remaining fuel is non-negative), they may visit planets in any order. In the end, they may stop on any planet, and they may even stop without ever leaving planet $P$. Their goal is to maximize the total amount of fuel collected. If there are multiple ways to achieve this goal, they also want to maximize the number of distinct planets they have visited. Can you help them?

The first line contains two integers $n, P$ separated by a space, representing the number of planets and the index of the starting planet. The next $n$ lines each contain two integers $a_i, b_i$.

Output consists of two lines, each containing one positive integer. The first line is the maximum total fuel the Fox Star Squad can collect when they stop. The second line is the maximum number of distinct planets they can visit, under the condition that they collect the amount of fuel stated in the first line.

One optimal plan is: after collecting the fuel on planet $2$ (the starting planet), the Fox Star Squad departs from there and visits planets $3, 1, 5$ in order, collecting fuel on each. The travel costs along the way are $3, 12, 15$ respectively. Starting from the initial planet, the remaining fuel after collecting on each planet is $10, 15, 15, 25$. At this point, they should not go to planet $4$, but should stop in order to maximize the total fuel collected at the end. For $20\%$ of the testdata, $1 \le n \le 10$. For $100\%$ of the testdata, $1 \le P \le n \le 10^5$, $a_i, b_i \le 10^5$. Translated by ChatGPT 5