CF436F 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 $ .

The first line contains two integers $ n $ and $ w $ $ (1

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