题目描述

城市 X 的地铁很特别：一列车只有一节车厢，而且车厢中只有一排 L 个座位。

共有 N 名乘客，编号为 0..N-1。每位乘客的“愉悦值”按如下方式计算：

• 如果该乘客站着，则愉悦值为 0；
• 如果该乘客坐着，则他获得：
  • 基础愉悦值 A[i]；
  • 以及额外愉悦值：对他左右两侧，直到遇到相邻乘客或座位排端点之间的空座位数，每个空位再贡献 B[i]。

例如，设有 3 位乘客 0,1,2，参数分别为：

• A[0]=5, B[0]=2
• A[1]=10, B[1]=1
• A[2]=1, B[2]=1

若 L=6，座位安排如下：

_ 0 _ _ 1 _

其中 _ 表示空座位，乘客 2 站立。

则：

• 乘客 0：坐下得 5，左右各有 1 与 2 个空位，因此额外得 3 * 2 = 6，总计 11；
• 乘客 1：坐下得 10，左右各有 2 与 1 个空位，因此额外得 3 * 1 = 3，总计 13；
• 乘客 2：站立，得 0。

总愉悦值为 24。

给定 L、N 以及每位乘客的 A[i], B[i]，请对于每个 K = 1..N，求出：恰有 K 名乘客坐下时，所有乘客总愉悦值的最大可能值。

若 K > L，显然无合法安排，答案为 0。

输入格式

第一行两个整数 N, L，表示乘客数与座位数。

接下来 N 行，每行两个非负整数 A[i], B[i]，表示第 i 名乘客的参数。

输出格式

输出 N 行。

第 K 行输出恰有 K 名乘客坐下时的最大总愉悦值。

若 K > L，输出 0。

数据范围

• 1 <= N <= 100000
• 1 <= L <= 200000
• 0 < A[i], B[i] < 10^9

子任务

• 子任务 1（20 分）：1 <= N <= 200
• 子任务 2（30 分）：1 <= N <= 5000
• 子任务 3（50 分）：无额外限制

只有通过某个子任务中的全部测试，才能获得该子任务分数。

样例 1

输入

3 2
1 2
3 4
5 6

输出

11
8
0

说明

当 K = 2 时，最优安排是乘客 1 与乘客 2 坐下且相邻，此时：

• 乘客 1 得到 3 + 0 * 4 = 3
• 乘客 2 得到 5 + 0 * 6 = 5
• 乘客 0 站立，得到 0

总和为 8。

样例 2

输入

3 3
1 2
3 4
5 100

输出

205
112
9

说明

当 K = 1 时，最优安排为：

2 _ _

总愉悦值为：

0 + 0 + (5 + 2 * 100) = 205