Description

有 $n$ 个物品，每个物品有一个体积 $w_i$ 和价值 $v_i$，现在要求对 $V \in [1,m]$，求出体积为 $V$ 的背包能够装下的最大价值。

Format

Input

第一行两个整数 $n$ 和 $m$，表示物品数量和最大体积。
接下来 $n$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 个物品的体积和价值。

Output

一行 $m$ 个整数，第 $i$ 个整数表示 $V=i$ 时能装下的最大价值。

Samples

3 5
2 3
3 4
4 5

0 3 4 5 7

数据范围

$n \leq 10^5$, $m \leq 10^3$, $1 \leq w_i \leq 300$, $1 \leq v_i \leq 10$。