SP23806 YOSSY - Yossy, The King of IRYUDAT

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.

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.

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