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;
inline int Read() {
  char c = getchar();
  int num = 0;
  while ('0' > c || c > '9') c = getchar();
  while ('0' <= c && c <= '9') num = num * 10 + c - '0', c = getchar();
  return (num);
}
long long nm[300010];
int n, s, pr[300010], nx[300010], v[300010], tb, tot;
struct Heap {
  pair<int, int> a[1010];
  int sz;
  inline void Clear() { sz = 0; }
  inline void Up(int x) {
    for (; x > 1 && a[x] < a[x / 2]; x /= 2) swap(a[x], a[x / 2]);
  }
  inline void Down(int x) {
    for (int s = x * 2; s <= sz; s = x * 2) {
      if (s + 1 <= sz && a[s] > a[s + 1]) s++;
      if (a[s] < a[x])
        swap(a[x], a[s]), x = s;
      else
        break;
    }
  }
  inline void Push(pair<int, int> x) {
    a[++sz] = x;
    Up(sz);
  }
  inline void Pop() {
    a[1] = a[sz];
    a[sz--] = make_pair(0, 0);
    Down(1);
  }
};
struct Bolck {
  Heap hp;
  int tim, top, q[410], st, ed, L, R;
  inline pair<long long, int> Ask() {
    return (make_pair(nm[nx[st]] + tim * 1ll * nx[st], nx[st]));
  }
  inline int Cal_tim(int x, int y) {
    long long nx = nm[x], ny = nm[y];
    long long dl = (long long)(nx - ny + y - x - 1) / (long long)(y - x);
    return ((dl <= n) ? (dl) : (n + 1));
  }
  inline void Cov() {
    tim++;
    pair<int, int> nw;
    while (hp.sz && hp.a[1].first <= tim) {
      nw = hp.a[1], hp.Pop();
      int ii = nw.second;
      if (v[ii]) continue;
      v[ii] = 1;
      nx[pr[ii]] = nx[ii], pr[nx[ii]] = pr[ii];
      if (pr[ii] == st || nx[ii] == ed) continue;
      int t = Cal_tim(pr[ii], nx[ii]);
      if (t <= n) hp.Push(make_pair(t, pr[ii]));
    }
  }
  inline void Add(int x) {
    hp.Clear();
    v[q[top = 1] = L] = 0;
    for (int i = L; i <= x; i++) nm[i] += i;
    for (int i = L + 1; i <= R; i++) {
      while (top && nm[q[top]] + tim * 1ll * q[top] <= nm[i] + tim * 1ll * i)
        top--;
      q[++top] = i, v[i] = 0;
    }
    pr[q[1]] = st, nx[st] = q[1];
    pr[ed] = q[top], nx[q[top]] = ed;
    for (int i = 1; i < top; i++) nx[q[i]] = q[i + 1];
    for (int i = 2; i <= top; i++) pr[q[i]] = q[i - 1];
    for (int i = 1; i < top; i++) {
      int t = Cal_tim(q[i], q[i + 1]);
      if (t <= n) hp.Push(make_pair(t, q[i]));
    }
  }
} b[410];
pair<long long, int> ans;
int w, ma, mb;
inline void Add(int x) {
  for (int i = 1; i <= tb; i++) {
    if (b[i].L > x) break;
    if (b[i].R <= x)
      b[i].Cov();
    else
      b[i].Add(x);
  }
}
inline void Solve() {
  ans = make_pair(0, 0);
  for (int i = 1; i <= tb; i++) {
    pair<long long, int> ab = b[i].Ask();
    if (ans.first < ab.first) ans = ab;
  }
}
inline void Prepare() {
  s = (int)(sqrt(ma) + .5), tot = ma;
  for (int i = 0; i <= ma; i += s) {
    b[++tb].L = i, b[tb].R = min(ma, i + s - 1);
    b[tb].st = ++tot, b[tb].ed = ++tot;
    b[tb].Add(-1);
    if (b[tb].R >= ma) break;
  }
}
struct Node {
  int a, b;
} a[300010];
bool Cmpb(Node a, Node b) { return (a.b < b.b); }
int main() {
  n = Read(), w = Read();
  for (int i = 1; i <= n; i++) {
    a[i].a = Read(), a[i].b = Read();
    mb = max(mb, a[i].b), ma = max(ma, a[i].a);
  }
  sort(a + 1, a + 1 + n, Cmpb);
  Prepare();
  for (int j = 1, i = 0; i <= mb + 1; i++) {
    while (a[j].b < i && j <= n) Add(a[j].a), j++;
    Solve();
    ans.first += (n - j + 1) * 1ll * i * w;
    printf("%I64d %d\n", ans.first, ans.second);
  }
}