Problem: 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.

<image>

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: ai — the number of rubles this user is willing to pay for the paid version of the application, and bi — 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 bi is at least c, then he uses the free version, 
  * otherwise, if value ai 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 bi) + 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 ≤ 105; 1 ≤ w ≤ 105) — the number of users and the profit from a single banner. Each of the next n lines contains two integers ai and bi (0 ≤ ai, bi ≤ 105) — the characteristics of the i-th user.

Output

Print (max bi) + 2 lines, in the i-th line print two integers: pay — the maximum gained profit at c = i - 1, p (0 ≤ p ≤ 109) — the corresponding optimal app cost. If there are multiple optimal solutions, print any of them.

Examples

Input

2 1
2 0
0 2


Output

0 3
3 2
4 2
2 2


Input

3 1
3 1
2 2
1 3


Output

0 4
3 4
7 3
7 2
4 2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct ww {
  long long x, y;
} c[400][400];
int i, j, k, n, m, ma, ren, C, kuai;
int cov[400], zhi[400];
long long b[400][400], s[400][400];
vector<int> a[100010];
inline void gao(int x) {
  int i, n = kuai - 1, g[400], r = 0;
  long long jum[400];
  for (i = 0; i <= n; i++) b[x][i] += cov[x];
  cov[x] = 0;
  s[x][0] = b[x][0];
  for (i = 1; i <= n; i++) s[x][i] = s[x][i - 1] + b[x][i];
  for (i = 0; i <= n; i++) {
    long long A = s[x][i], F = 0;
    for (; r; r--) {
      int wei = g[r];
      long long B = s[x][wei];
      int cha = i - wei;
      if (A >= B) continue;
      long long ci = (B - A) / cha + ((B - A) % cha > 0);
      if (jum[r] >= ci)
        continue;
      else {
        F = ci;
        break;
      }
    }
    g[++r] = i, jum[r] = F;
  }
  jum[r + 1] = 100010;
  for (i = 1; i <= r; i++) c[x][i] = (ww){g[i], jum[i + 1]};
  zhi[x] = 1;
}
inline void jian(int x) {
  int A = x / kuai, B = x % kuai;
  b[A][B] -= x;
  gao(A);
}
inline void jia(int x) {
  if (x < 0) return;
  int A = x / kuai, B = x % kuai, i;
  for (i = 0; i <= A - 1; i++) {
    cov[i]++;
    if (c[i][zhi[i]].y == cov[i]) zhi[i]++;
  }
  for (i = 0; i <= B; i++) b[A][i]++;
  gao(A);
}
inline long long suan(int x) {
  ww A = c[x][zhi[x]];
  return s[x][A.x] + 1ll * cov[x] * (A.x + 1);
}
inline ww cal() {
  int i, id;
  long long ma, sum;
  ma = -1, sum = 0;
  for (i = 0; i <= 400 - 1; i++) {
    long long re = sum + suan(i);
    if (re > ma) ma = re, id = i * kuai + c[i][zhi[i]].x;
    sum += s[i][kuai - 1] + 1ll * cov[i] * kuai;
  }
  return (ww){ma, id};
}
int main() {
  kuai = 300;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[y].push_back(x - 1);
    ma = max(ma, y);
  }
  for (i = 0; i <= 400 - 1; i++) gao(i);
  ren = n;
  for (C = 0; C <= ma + 1; C++) {
    ww re = cal();
    printf("%I64d %I64d\n", 1ll * ren * C * m + re.x, re.y + 1);
    for (j = 0; j < a[C].size(); j++) {
      int A = a[C][j];
      ren--;
      jia(A);
      jian(A + 1);
    }
  }
  return 0;
}