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 maxN = 100000 + 100;
pair<int, int> P[maxN];
int toAdd[maxN], cnt[500], rec[500][500];
long long old[maxN];
int main() {
  ios::sync_with_stdio(0);
  int n, w;
  cin >> n >> w;
  int maxB = 0, maxA = 0;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    P[i] = make_pair(b, a);
    maxB = max(maxB, b);
    maxA = max(maxA, a);
  }
  sort(P, P + n);
  int blk;
  for (blk = 1; (blk + 1) * (blk + 1) <= maxA; ++blk)
    ;
  int cntBlk = maxA / blk + 1;
  for (int c = 0, cur = 0; c <= maxB + 1; ++c) {
    for (; cur < n && P[cur].first < c; ++cur) {
      int a = P[cur].second, m = a / blk;
      for (int i = 0; i < m; ++i) toAdd[i] += 1;
      for (int i = m * blk; i <= a; ++i) old[i] += i;
      cnt[m] = 0;
      int *Rec = rec[m], &Cnt = cnt[m];
      for (int i = m * blk; i < (m + 1) * blk && i <= maxA; ++i) {
        while (Cnt > 0 && old[i] >= old[Rec[Cnt - 1]]) --Cnt;
        while (Cnt > 1 && (old[(Rec[Cnt - 2])] - old[i]) *
                                  ((Rec[Cnt - 1]) - (Rec[Cnt - 2])) <=
                              (old[(Rec[Cnt - 2])] - old[(Rec[Cnt - 1])]) *
                                  (i - (Rec[Cnt - 2])))
          --Cnt;
        Rec[Cnt++] = i;
      }
    }
    long long opt = 0;
    int optP = 0;
    for (int i = 0; i < cntBlk; ++i) {
      if (!cnt[i]) continue;
      int l = 0, r = cnt[i] - 1, curP;
      while (l + 3 <= r) {
        int mid = (l + r) >> 1;
        if ((1ll * toAdd[i] * rec[i][mid] + old[rec[i][mid]]) >
            (1ll * toAdd[i] * rec[i][mid + 1] + old[rec[i][mid + 1]]))
          r = mid;
        else
          l = mid;
      }
      for (curP = l++; l <= r; ++l)
        if ((1ll * toAdd[i] * rec[i][l] + old[rec[i][l]]) >
            (1ll * toAdd[i] * rec[i][curP] + old[rec[i][curP]]))
          curP = l;
      if ((1ll * toAdd[i] * rec[i][curP] + old[rec[i][curP]]) > opt)
        opt = (1ll * toAdd[i] * rec[i][curP] + old[rec[i][curP]]),
        optP = rec[i][curP];
    }
    cout << 1ll * c * w * (n - cur) + opt << " " << optP << endl;
  }
  return 0;
}