Problem Statement

You have decided to practice. Practice means solving a large number of problems in AtCoder. Practice takes place over several days. The practice for one day is carried out in the following steps.

• Let $M$ be the number of problems to be solved on that day. Each problem has a value called difficulty, which is a pair of non-negative integers $(A, B)$.
• First, rearrange the $M$ problems in any order. Then, solve the problems one by one in that order.
• You have a value called fatigue. The fatigue at the beginning of the day is $0$, and it changes from $x$ to $Ax + B$ when solving a problem with difficulty $(A, B)$.
• The fatigue at the end of solving all $M$ problems is called the energy consumed for that day.

There is a sequence of $N$ problems in AtCoder, called problem $1$, problem $2$, $\dots$, problem $N$ in order. The difficulty of problem $i$ is $(A_i, B_i)$. You have decided to solve all $N$ problems through practice. Practice is carried out in the following steps. Below, let $[L, R]$ denote the following sequence of problems: problem $L$, problem $L+1$, $...$, problem $R$.

• Choose an integer $K$ freely between $1$ and $N$, inclusive. The practice will last $K$ days.
• Divide the sequence of $N$ problems into $K$ non-empty continuous subsequences, and let $S_i$ be the $i$-th sequence. Formally, choose a strictly increasing non-negative integer sequence $x_0, x_1, \dots, x_K$ such that $1 = x_0$ and $x_K = N + 1$, and let $S_i = [x_{i-1}, x_i - 1]$ for $1 \leq i \leq K$.
• Then, for $i=1, 2, \dots, K$, solve all problems in $S_i$ on the $i$-th day of practice.

You have decided to practice so that the total energy consumed throughout the practice is at most $X$. Let $D$ be the minimum possible value of $K$, the number of days, for such a practice. (Here, it is guaranteed that $\sum_{i = 1}^N B_i \leq X$. Under this constraint, such $D$ always exists.) Also, let $M$ be the minimum possible total energy consumed throughout a practice such that $K=D$.

Find $D$ and $M$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq X \leq 10^8$
• $1 \leq A_i \leq 10^5$
• $1 \leq B_i$
• $\sum_{i=1}^N B_i \leq X$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print $D$ and $M$ separated by a space.