#ABC388B. [ABC388B]沉重的蛇

[ABC388B]沉重的蛇

问题陈述

NN条蛇。

ii条蛇的直径是TiT_i厘米,长度是LiL_i厘米。

蛇的重量是粗细和长度的乘积。

对于满足1kD1 \leq k \leq D的每个整数kk,当所有蛇的长度都增加kk厘米时,求最大的蛇的重量。

约束

  • 1N,D1001\leq N, D\leq 100
  • 1Ti,Li1001\leq T_i, L_i\leq 100
  • 所有输入都是整数

输入

输入以以下形式从标准输入给出:

NN DD T1T_1 L1L_1 T2T_2 L2L_2 \vdots TNT_N LNL_N

输出

DD行输出。第kk行输出当所有蛇的长度增加kk时最重的蛇的重量。

输入样例

4 3
3 3
5 1
2 4
1 10

输出样例

12
15
20