Banners

5000ms

524288K

Description:

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.

$\text{[math]}$

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.

Sample Input:

2 1
2 0
0 2

Sample Output:

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF436F