This problem deals with the simple knapsack problem.

You are required to find the set of of items that goes into the knapsack for which the value is maximized. The input will contain the number of items, value, space taken up by each item, and the total capacity of the knapsack.

Input

The input will contain three lines. The first line will an integer n, which is the number of items you have to consider. The second line will contain n pairs of space, value each indicating how much it costs to put the item inside the knapsack, and how much value it has for the knapsack. The third line will contain a single integer, C that is the total capacity of the knapsack.

Output

You are required to print m space separated integers, which are in non decreasing order, of the item costs that will be put in the knapsack for maximum value. (The items must add up to be less than or equal to the knapsack capacity).

Example

Input:
10
2 3 4 3 8 3 2 3 4 3 10 3 12 3 7 3 9 3 15 3
19

Output:
2 2 4 4 7

Scoring method

Please note that apart from the sample test case posted here, there will be other hidden test cases that your code will checked on. The final score you see is a percentage of the test cases you have passed. If you pass only the sample test case, you will get 0/100 (even though your score will be shown as 10/100).

Each of these questions are finally worth the points mentioned in the assignment pdf file. So your credit for this problem shall be your score/100 * points for this question. Your final credit for programming assignment 3 shall be final score / 55 * 100.

Plagiarism and Copying

Strict action will be taken against students who are found to be indulging in plagiarism. Please note that changing variable names, removing indentation or moving code around will not help with regards to plagiarism checking.