Yossy is the king of IRYUDAT kingdom. The kingdom lives peacefully because Yossy is kind and wise. One day, the enemy wants to launch an attack on IRYUDAT. So, the enemy prepares a strong army to crush IRYUDAT kingdom.

Yossy knows about this. He must protect his kingdom. The most logical way to prevent this is to send an army that is at least as strong as the enemy’s army. An army’s power is the sum of each soldier’s power. For example if there are three soldiers with 10, 20, and 25 power respectively, the army’s power is 55.

Yossy gathers all of his soldiers. To make a powerful army, he can simply choose soldiers with high power or just send them all. However, this can’t be done because the soldiers need to eat. Each soldier has to eat a certain amount of food or they can’t go to war. Unfortunately, the kingdom is currently lacking food supply. Yossy needs to choose soldiers wisely so he can make a powerful army with the food limitation.

Another problem occurs. Yossy doesn’t know the enemy's power. So, he sends his underling to calculate the enemy’s power. He wants to have a list of his possible army's powers, sorted from the best to the worst, so that after he knows the enemy’s power, he can send an army that is at least as strong as the enemy’s. Two armies are different if the combination of the soldiers is different.

Input

First line contains an integer n (1 ≤ n ≤ 2000), the number of soldiers that Yossy has. The next n lines contain p (0 ≤ p ≤ 9999) and f (0 ≤ f ≤ 9999), the power and food portion of each soldier. The next line contains s (0 ≤ s ≤ 999999), the maximum food supply. The last line contains k (1 ≤ k ≤ 40), the length of Yossy’s list. If no more combination of soldiers are available, output 0 until the end of the list.

For test data with n > 15, the p and f value will be randomly generated with no correlation.

Output

k lines containing the army’s power from the first best to k-best army.

Example

Input:
4
45 3
30 5
45 9
10 5
15
4

Output:
90
85
75
75

Explanation

The 1st best army has power 90. It can be obtained from soldier 1 and 3, with sum of power 90 and sum of food portion 12.
The 2nd best army has power 85. It can be obtained from soldier 1, 2, and 4 with sum of power 85 and sum of food portion 13.
The 3rd best army has power 75. It can be obtained from soldier 1 and 2, with sum of power 75 and sum of food portion 8.
The 4th best army has power 75. It can be obtained from soldier 2 and 3, with sum of power 75 and sum of food portion 14.
Note that the 3rd and 4th best army have same power but the combination of soldiers is different.