Zepto Code Rush 2014 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

dp

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Banners

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAll 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^{5}; 1 ≤ *w* ≤ 10^{5}) — 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^{5}) — 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^{9}) — 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2023 17:01:41 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|