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

Input 1

1 100
20 1

Output 1

20

Input 2

2 60
20 3
5 1

Output 2

5 20 25 40 45 60