F. Banners
brute force; data structures; dp
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: 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.
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.
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.