Banners

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.

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: a _i — the number of rubles this user is willing to pay for the paid version of the application, and b _i — 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 b _i is at least c, then he uses the free version,
• otherwise, if value a _i 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 b _i) + 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 ≤ 10⁵; 1 ≤ w ≤ 10⁵) — the number of users and the profit from a single banner. Each of the next n lines contains two integers a _i and b _i (0 ≤ a _i, b _i ≤ 10⁵) — the characteristics of the i-th user.

Output

Print (max b _i) + 2 lines, in the i-th line print two integers: pay — the maximum gained profit at c = i - 1, p (0 ≤ p ≤ 10⁹) — 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:

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const int MAX = 100200;
const int BLOCK_SIZE = 300;
const int BLOCK_CNT = MAX / BLOCK_SIZE;

pair <int, int> user[MAX];

int sz[BLOCK_CNT];
int st[BLOCK_CNT][BLOCK_SIZE + 10];
long double sx[BLOCK_CNT][BLOCK_SIZE + 10];
int ptr[BLOCK_CNT];

long long bmax[BLOCK_CNT];
int bid[BLOCK_CNT];
int badd[BLOCK_CNT];

int a[MAX];

long double intersect(int i, int j) {
return 1.0 * ((long long)i * a[i] - (long long)j * a[j]) / (j - i);
}

long long pay[MAX];
int opt[MAX];

int main() {
int n, w;
scanf("%d %d", &n, &w);
for (int i = 0; i < n; i++) {
    scanf("%d %d", &user[i].second, &user[i].first);
  }
  sort(user, user + n);
  int maxbi = user[n - 1].first;
  for (int i = 0; i < MAX; i++) {
    a[i] = 0;
  }
  for (int b = 0; b < BLOCK_CNT; b++) {
    bmax[b] = 0;
    bid[b] = b * BLOCK_SIZE;
    badd[b] = 0;
  }
  int j = 0;
  for (int C = 0; C <= maxbi + 1; C++) {
    while (j < n) {
      if (user[j].first >= C) {
break;
}
int pos = user[j].second;
for (int b = 0; b < BLOCK_CNT; b++) {
        int from = b * BLOCK_SIZE;
        int to = from + BLOCK_SIZE;
        if (pos >= to) {
badd[b]++;
while (ptr[b] < sz[b] && badd[b] > sx[b][ptr[b]]) {
ptr[b]++;
}
int q = st[b][ptr[b]];
bmax[b] = (long long)q * (a[q] + badd[b]);
bid[b] = q;
} else {
for (int i = from; i < to; i++) {
            a[i] += badd[b];
          }
          for (int i = from; i <= pos; i++) {
            a[i]++;
          }
          badd[b] = 0;
          sz[b] = 0;
          for (int i = from; i < to; i++) {
            while (sz[b] >= 2) {
long double u = intersect(i, st[b][sz[b]]);
if (u < sx[b][sz[b] - 1]) {
                sz[b]--;
              } else {
                break;
              }
            }
            st[b][++sz[b]] = i;
            if (sz[b] >= 2) {
sx[b][sz[b] - 1] = intersect(i, st[b][sz[b] - 1]);
}
}
ptr[b] = 1;
while (ptr[b] < sz[b] && 0 > sx[b][ptr[b]]) {
ptr[b]++;
}
int q = st[b][ptr[b]];
bmax[b] = (long long)q * a[q];
bid[b] = q;
break;
}
}
j++;
}
pay[C] = -1;
opt[C] = -1;
for (int b = 0; b < BLOCK_CNT; b++) {
      if (bmax[b] > pay[C]) {
pay[C] = bmax[b];
opt[C] = bid[b];
}
}
pay[C] += C * 1LL * w * (n - j);
}
for (int C = 0; C <= maxbi + 1; C++) {
    printf("%I64d %d\n", pay[C], opt[C]);
  }
  return 0;
}