Description

有$n$个物品和一个体积为$m$的背包，每个物品有一个价值$v_i$，和体积$t_i$，选择若干物品，使得体积之和不超过$m$的情况下价值之和最大。

对于任意第$i$个物品，求第$i$个物品一定不在背包时的最大价值。

Format

Input

第一行两个正整数$n(n\leq 5000)$和$m(m\leq 5000)$，其含义见题目描述。

接下来$n$行，第i行两个正整数$t_i(t_i \leq 100)$和$v_i(v_i \leq 100)$分别代表第i件物品的体积和价值。

Output

一行，$n$个数字，其中第$i$个数字代表第$i$个物品一定不在背包时的最大价值。

Samples

5 10
2 10
5 100
2 6
7 25
4 8

108 35 110 116 116

Limitation

1s, 1024KiB for each test case.