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 inf = int(1e9);
const double eps = 1e-9;
const double pi = 4 * atan(double(1));
const int BLOCK = 300;
const int N = int(1e5) + 100;
struct point {
  long long x, y;
  point() {}
  point(long long x, long long y) {
    this->x = x;
    this->y = y;
  }
};
bool operator<(const point &a, const point &b) {
  return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
point operator-(const point &a, const point &b) {
  return point(a.x - b.x, a.y - b.y);
}
int k;
pair<int, int> a[N];
int b[N], c[N];
int add[N / BLOCK + 10], sz[N / BLOCK + 10];
pair<long long, int> res[N / BLOCK + 10];
point p[N / BLOCK + 10][BLOCK + 10];
inline long long vec(point &a, point &b) { return a.x * b.y - b.x * a.y; }
inline bool bad(point &a, point &b, point &c) {
  point v1 = b - a, v2 = c - b;
  return vec(v1, v2) >= 0;
}
inline void build(int num) {
  sz[num] = 0;
  res[num] = make_pair(-1LL, -1);
  for (int i = num * BLOCK; i < min((num + 1) * BLOCK, k); ++i) {
    res[num] = max(res[num], make_pair(1LL * b[i] * c[i], b[i]));
    p[num][sz[num]++] = point(b[i], 1LL * b[i] * c[i]);
  }
  sort(p[num], p[num] + sz[num]);
  int oldSz = sz[num];
  sz[num] = 0;
  for (int i = 0; i < oldSz; ++i) {
    while (sz[num] >= 2 &&
           bad(p[num][sz[num] - 2], p[num][sz[num] - 1], p[num][i])) {
      --sz[num];
    }
    p[num][sz[num]++] = p[num][i];
  }
}
inline void addP(int p) {
  int pos = lower_bound(b, b + k, p) - b;
  int num = pos / BLOCK;
  for (int i = 0; i < num; ++i) {
    ++add[i];
  }
  for (int i = num * BLOCK; i < min((num + 1) * BLOCK, k); ++i) {
    c[i] += add[num];
  }
  for (int i = num * BLOCK; i <= pos; ++i) {
    ++c[i];
  }
  add[num] = 0;
  build(num);
}
inline pair<long long, int> get(int num) {
  if (add[num] == 0) {
    return res[num];
  }
  int ptr = sz[num] - 1, l = 0, r = sz[num] - 2;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (p[num][mid].y + p[num][mid].x * add[num] >=
        p[num][mid + 1].y + p[num][mid + 1].x * add[num]) {
      ptr = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  pair<long long, int> res =
      make_pair(p[num][ptr].y + p[num][ptr].x * add[num], p[num][ptr].x);
  res = max(res,
            make_pair(p[num][sz[num] - 1].y + p[num][sz[num] - 1].x * add[num],
                      int(p[num][sz[num] - 1].x)));
  res = max(res,
            make_pair(p[num][0].y + p[num][0].x * add[num], int(p[num][0].x)));
  return res;
}
int main() {
  int n, w;
  scanf("%d %d", &n, &w);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &a[i].second, &a[i].first);
    b[i] = a[i].second;
  }
  sort(a, a + n);
  sort(b, b + n);
  k = unique(b, b + n) - b;
  for (int i = 0; i * BLOCK < k; ++i) {
    build(i);
  }
  int ptr = 0;
  for (int c = 0; c <= a[n - 1].first + 1; ++c) {
    while (ptr < n && a[ptr].first < c) {
      addP(a[ptr++].second);
    }
    pair<long long, int> res(0LL, b[k - 1] + 1);
    for (int j = 0; j * BLOCK < k; ++j) {
      res = max(res, get(j));
    }
    res.first += 1LL * (n - ptr) * c * w;
    printf(
        "%lld"
        " %d\n",
        res.first, res.second);
  }
  return 0;
}