Where's That Fuel?

Interview

Time limit2sMemory limit256 MB

Summary

Starting with planet P's fuel, repeatedly visit affordable planets to maximize final fuel, then the number of visits.

Level: Medium5 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

Team Star Fox collects fuel from N planets. Planet i has Ai fuel cells, and travelling there from anywhere costs Bi fuel. Each planet yields fuel only once. Starting at planet P, they collect its fuel immediately, then may visit other planets in any order while fuel never goes negative. Maximize final fuel, then maximize planets visited among optimal tours.

Input

The first line has N and P. The next N lines contain Ai and Bi.

Output

Print the maximum fuel on the first line and the maximum number of visited planets on the second.

Examples2

Example 1
Input
```
5 2
12 12
10 100
8 3
4 5
25 15
```
Expected output
```
25
4
```
Example 2
Input
```
1 1
5 10
```
Expected output
```
5
1
```