All modern mobile applications are divided into free and paid. Even a single application developers often release two versions: a paid version without ads and a free version with ads.

Suppose that a paid version of the app costs $*p*$ ($*p*$ is an integer) rubles, and the free version of the application contains $*c*$ ad banners. Each user can be described by two integers: $*a*_{*i*}$ — the number of rubles this user is willing to pay for the paid version of the application, and $*b*_{*i*}$ — the number of banners he is willing to tolerate in the free version.

The behavior of each member shall be considered strictly deterministic:

• if for user $*i*$, value $*b*_{*i*}$ is at least $*c*$, then he uses the free version,
• otherwise, if value $*a*_{*i*}$ is at least $*p*$, then he buys the paid version without advertising,
• otherwise the user simply does not use the application.

Each user of the free version brings the profit of $*c* × *w*$ rubles. Each user of the paid version brings the profit of $*p*$ rubles.

Your task is to help the application developers to select the optimal parameters $*p*$ and $*c*$. Namely, knowing all the characteristics of users, for each value of $*c*$ from $0$ to $(*max* *b*_{*i*}) + 1$ you need to determine the maximum profit from the application and the corresponding parameter $*p*$.

Input

The first line contains two integers $*n*$ and $*w*$ $(1 ≤ *n* ≤ 10^{5}; 1 ≤ *w* ≤ 10^{5})$ — the number of users and the profit from a single banner. Each of the next $*n*$ lines contains two integers $*a*_{*i*}$ and $*b*_{*i*}$ $(0 ≤ *a*_{*i*}, *b*_{*i*} ≤ 10^{5})$ — the characteristics of the $*i*$-th user.

Output

Print $(*max* *b*_{*i*}) + 2$ lines, in the $*i*$-th line print two integers: $*pay*$ — the maximum gained profit at $*c* = *i* - 1$, $*p*$ $(0 ≤ *p* ≤ 10^{9})$ — the corresponding optimal app cost. If there are multiple optimal solutions, print any of them.