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;
double intersect(const vector<long long>& d, int i, int j) {
  return (d[i] - d[j] + 0.0) / (j - i);
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, w;
  cin >> n >> w;
  int A = 0;
  vector<pair<pair<int, int>, int> > p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i].first.second >> p[i].first.first;
    A = max(A, p[i].first.second);
    p[i].second = i;
  }
  sort(p.begin(), p.end());
  int cur = 0;
  vector<pair<int, int> > query;
  for (int c = 0; c <= p.back().first.first + 1; ++c) {
    while (cur < n && p[cur].first.first == c - 1) {
      query.push_back(make_pair(0, p[cur].first.second));
      ++cur;
    }
    query.push_back(make_pair(1, c));
  }
  vector<long long> d(A + 1);
  vector<pair<long long, long> > ans;
  int block_size = sqrt(query.size() + 0.0);
  int people_count = n;
  for (int pos = 0; pos < query.size(); pos += block_size) {
    int end_pos = min((int)query.size(), pos + block_size);
    vector<int> add;
    for (int i = pos; i < end_pos; ++i) {
      if (query[i].first == 0 && query[i].second > 0)
        add.push_back(query[i].second);
    }
    sort(add.begin(), add.end());
    vector<pair<int, int> > segment;
    if (add.size() > 0) segment.push_back(make_pair(1, add[0]));
    for (int i = 0; i + 1 < add.size(); ++i) {
      if (add[i] + 1 <= add[i + 1])
        segment.push_back(make_pair(add[i] + 1, add[i + 1]));
    }
    if (add.size() > 0 && add.back() < A)
      segment.push_back(make_pair(add.back() + 1, A));
    if (segment.size() == 0) segment.push_back(make_pair(1, A));
    vector<long long> coef(segment.size()), position(segment.size(), -1);
    vector<vector<pair<double, int> > > envelope(segment.size());
    for (int i = 0; i < segment.size(); ++i) {
      for (int j = segment[i].first + 1; j <= segment[i].second; ++j) {
        while (!envelope[i].empty() &&
               intersect(d, j, envelope[i].back().second) <
                   envelope[i].back().first)
          envelope[i].pop_back();
        if (envelope[i].empty())
          envelope[i].push_back(
              make_pair(intersect(d, segment[i].first, j), j));
        else
          envelope[i].push_back(
              make_pair(intersect(d, j, envelope[i].back().second), j));
      }
      int k = 0;
      while (k < envelope[i].size() && envelope[i][k].first < 0) ++k;
      position[i] = k - 1;
    }
    for (int i = pos; i < end_pos; ++i) {
      if (query[i].first == 0) {
        --people_count;
        if (query[i].second == 0) continue;
        int k = 0;
        while (k < segment.size() && segment[k].second <= query[i].second) {
          ++coef[k];
          int st = position[k] + 1;
          while (st < envelope[k].size() &&
                 envelope[k][st].first < coef[k] + 0.0)
            ++st;
          position[k] = st - 1;
          ++k;
        }
      } else {
        long long cur_ans = -1, price = -1;
        for (int k = 0; k < segment.size(); ++k) {
          long long current = 0;
          if (position[k] == -1)
            current = d[segment[k].first] + coef[k] * segment[k].first;
          else
            current = d[envelope[k][position[k]].second] +
                      coef[k] * envelope[k][position[k]].second;
          if (cur_ans == -1 || cur_ans < current) {
            cur_ans = current;
            if (position[k] == -1)
              price = segment[k].first;
            else
              price = envelope[k][position[k]].second;
          }
        }
        ans.push_back(make_pair(
            cur_ans + (long long)w * people_count * query[i].second, price));
      }
    }
    for (int i = 0; i < segment.size(); ++i) {
      for (int j = segment[i].first; j <= segment[i].second; ++j)
        d[j] += coef[i] * j;
    }
  }
  for (int i = 0; i < ans.size(); ++i)
    cout << ans[i].first << " " << ans[i].second << "\n";
  return 0;
}