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;
const int N = 1e5 + 50;
const int B = 280;
struct Line {
  int k;
  long long b;
  Line(int _k = 0, long long _b = 0) : k(_k), b(_b) {}
  inline long long calc(long long x) { return x * k + b; }
  inline long long inter(Line o) { return (b - o.b) / (o.k - k); }
} swp[1000];
long long effect[1000];
int n, w, m, cpos, fix[N];
vector<int> tab[N];
long long base[N], cur;
struct Blo {
  int l, r;
  int k[B + 10], tag, ptr;
  long long cval, b[B + 10], a[B + 10];
  Blo() {
    a[1] = 0;
    b[1] = 0;
    a[2] = 1e9;
    ptr = 1;
    tag = cval = 0;
  }
  inline void nextX() {
    tag++;
    if (tag >= a[ptr + 1])
      cval = b[++ptr];
    else
      cval += k[ptr];
    if (cval > cur) {
      cur = cval;
      cpos = k[ptr];
    }
  }
  inline void rebuild(int p) {
    for (int i = l; i <= r; i++) base[i] += 1ll * (tag + (i <= p)) * i;
    int top = 0;
    Line bra;
    for (int i = l; i <= r; i++) {
      bra = Line(i, base[i]);
      while (top > 0 &&
             (swp[top].b <= bra.b || swp[top].inter(bra) < effect[top]))
        top--;
      if (!top) {
        effect[1] = 0;
        swp[top = 1] = bra;
      } else {
        effect[top + 1] = swp[top].inter(bra) + 1;
        swp[++top] = bra;
      }
    }
    for (int i = 1; i <= top; i++) {
      b[i] = swp[i].calc(effect[i]);
      k[i] = swp[i].k;
      a[i] = effect[i];
    }
    a[top + 1] = 1e9;
    ptr = 1;
    cval = b[1];
    tag = 0;
    if (cval >= cur) {
      cur = cval;
      cpos = k[1];
    }
  }
} b[N / B + 3];
inline void Insert(int x) {
  if (!x) return;
  for (int i = x / B; i; i--) b[i].nextX();
  if (x % B) b[(x - 1) / B + 1].rebuild(x);
}
int main() {
  int mxa = 0;
  scanf("%d%d", &n, &w);
  for (int i = 1, a, b; i <= n; i++) {
    scanf("%d%d", &a, &b);
    tab[b].push_back(a);
    m = max(m, b);
    mxa = max(mxa, a);
  }
  mxa++;
  int tot = (mxa - 1) / B + 1;
  for (int i = 1; i <= tot; i++) {
    b[i].k[1] = min(i * B, mxa);
    b[i].l = (i - 1) * B + 1;
    b[i].r = min(i * B, mxa);
  }
  for (int i = m; ~i; i--) fix[i] = fix[i + 1] + tab[i].size();
  for (int i = 0; i <= m + 1; i++) {
    printf("%lld %d\n", cur + 1ll * fix[i] * w * i, cpos);
    for (auto j : tab[i]) Insert(j);
  }
  return 0;
}