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 ith 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.</p>

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?

입력 형식

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

출력 형식

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.

예제 입력

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

예제 출력

25
4