Pondo Sums

Pondo Sums

Problem Statement

You are given some positive integers, you are told how many of each different integer you have. You are also given an integer $k$, determine the different integers under or equal to $k$ that you can make by summing up some subset of these integers (pick some and leave the others).

Input Format

Your first line will contain two space-separated integers $n$ and $k$, where $n$ is the number of unique integers you have (and $k$ is the same as in the problem statement). Your next $n$ lines will contain two integers each $a_i$ and $b_i$, meaning that you have $b_i$ many of the number $a_i$.

Output Format

Output a single line, containing all the numbers under or equal to $k$ that can be formed by summing some of the integers together.

Constraints

• $1 \leq n, k, a_i \leq 1000$
• $1 \leq b_i \leq 10^9$

Sample Cases

1 100
20 1

20

2 60
20 3
5 1

5 20 25 40 45 60