Seats

The subway in town X is a bit unusual. A train has a single wagon with one row of $L$ seats. The wagon holds $N$ passengers, numbered from $0$ to $N-1$. Each passenger gets pleasure as follows:

• If a passenger is standing, the pleasure is $0$.
• If a passenger is sitting, the passenger gets $A_i$ pleasure from sitting, plus $B_i$ pleasure for each empty seat between the passenger and a neighboring passenger or the end of the row.

For example, let there be 3 passengers with $A_0=5$, $B_0=2$, $A_1=10$, $B_1=1$, $A_2=1$, $B_2=1$, and let $L=6$. Consider this seating, where _ is an empty seat:

_ 0 _ _ 1 _

Passenger 2 is standing.

• Passenger 0 gets $5$ for sitting and $6$ for the empty seats (1 on the left and 2 on the right), for a total of $11$.
• Passenger 1 gets $10$ for sitting and $3$ for the empty seats (2 on the left and 1 on the right), for a total of $13$.
• Passenger 2 gets $0$ because the passenger is standing.

The total pleasure of all passengers is $24$.

Write a program that, given $N$, $L$, and the characteristics of each passenger, finds the maximum possible total pleasure for every number of seated passengers from $1$ to $N$.

The first line contains two integers $N$ and $L$, the number of passengers and the number of seats. Each of the next $N$ lines contains two non-negative integers $A_i$ and $B_i$ for passenger $i$.

Print $N$ lines. The $K$-th line contains the maximum total pleasure the passengers can get when exactly $K$ of them are sitting. For $K > L$, print $0$, because no valid configuration of $K$ passengers fits in $L$ seats.

• $1 \le N \le 100\,000$
• $1 \le L \le 200\,000$
• $0 < A_i, B_i < 10^9$