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;
long double det(const pair<long double, long double> &a,
                const pair<long double, long double> &b) {
  return (long long)a.first * b.second - (long long)b.first * a.second;
}
pair<long double, long double> operator-(
    const pair<long double, long double> &a,
    const pair<long double, long double> &b) {
  return pair<long double, long double>(a.first - b.first, a.second - b.second);
}
pair<long double, long double> operator*(
    const pair<long double, long double> &a, long double b) {
  return pair<long double, long double>(a.first * b, a.second * b);
}
pair<long double, long double> operator/(
    const pair<long double, long double> &a, long double b) {
  return pair<long double, long double>(a.first / b, a.second / b);
}
pair<long double, long double> intersect(
    const pair<long double, long double> &a,
    const pair<long double, long double> &b,
    const pair<long double, long double> &c,
    const pair<long double, long double> &d) {
  double k1 = det(b - a, c - a), k2 = det(b - a, d - a);
  if (fabs(k1 - k2) < 1e-10) return pair<long double, long double>(-1, -1);
  return (d * k1 - c * k2) / (k1 - k2);
}
const int MAXN = 100000 + 10, MAXT = 400 + 10, MAXL = 400;
long long Tohka;
int Mashiro;
int n, m, w, d[MAXT], pt[MAXT], C[MAXT][MAXT], Pn[MAXT], cnt[MAXT];
vector<int> a[MAXN];
pair<long double, long double> PP[MAXT][MAXT];
long double B[MAXT][MAXT];
bool cmp(const pair<long double, long double> &a,
         const pair<long double, long double> &b) {
  return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
}
long double calc(pair<long double, long double> a, long double first) {
  return a.first * a.second + first * a.first;
}
void Upd(int first) {
  pair<long double, long double> *p = PP[first];
  int *c = C[first], &ptr = pt[first];
  for (; ptr > 1 && calc(p[c[ptr - 1]], d[first]) > calc(p[c[ptr]], d[first]);
       --ptr)
    ;
  if ((long long)calc(p[c[ptr]], d[first]) > Tohka)
    Tohka = (long long)calc(p[c[ptr]], d[first]),
    Mashiro = (int)p[c[ptr]].first;
}
int cntx[MAXN];
void Ins(int first) {
  ++cntx[first];
  int bel = first / MAXL;
  int second = 1;
  for (int i = MAXT - 1; i > bel; --i) second += cnt[i];
  pair<long double, long double> *p = PP[bel];
  int *c = C[bel], &pn = Pn[bel];
  long double *b = B[bel];
  bool flag = 0;
  for (int j = 1; j <= pn; ++j)
    p[j].second += d[bel] + (p[j].first <= first),
        second += (p[j].first > first) * cntx[(int)p[j].first],
        flag |= (fabs(p[j].first - first) < 1e-10);
  d[bel] = 0;
  ++cnt[bel];
  if (!flag) p[++pn] = pair<long double, long double>(first, second);
  sort(p + 1, p + pn + 1, cmp);
  c[0] = 1, c[1] = pn;
  for (int i = pn - 1; i >= 1; --i) {
    if (p[i].first * p[i].second <= p[c[c[0]]].first * p[c[c[0]]].second)
      continue;
    for (; c[0] >= 2 && calc(p[c[c[0]]], b[c[0] - 1]) < calc(p[i], b[c[0] - 1]);
         --c[0])
      ;
    c[++c[0]] = i;
    b[c[0] - 1] =
        intersect(
            pair<long double, long double>(
                0, p[c[c[0]]].first * p[c[c[0]]].second),
            pair<long double, long double>(
                1, p[c[c[0]]].first * p[c[c[0]]].second + p[c[c[0]]].first),
            pair<long double, long double>(
                0, p[c[c[0] - 1]].first * p[c[c[0] - 1]].second),
            pair<long double, long double>(
                1, p[c[c[0] - 1]].first * p[c[c[0] - 1]].second +
                       p[c[c[0] - 1]].first))
            .first;
  }
  pt[bel] = c[0];
  Upd(bel);
  for (int i = 0; i < bel; ++i)
    if (Pn[i]) ++d[i], Upd(i);
}
int main() {
  cin >> n >> w;
  for (int i = 1; i <= n; ++i) {
    int first, second;
    cin >> first >> second;
    a[second].push_back(first);
    m = max(second + 1, m);
  }
  int res = n;
  for (int i = 0; i <= m; ++i) {
    cout << Tohka + (long long)i * w * res << " " << Mashiro << endl;
    for (int j = 0; j < (int)a[i].size(); ++j) Ins(a[i][j]), --res;
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}