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.
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 kbest 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.
hide comments
Vladyslav Hlembotskyi:
20170226 19:19:58
Quite strange problem.


nikola117:
20160415 18:45:01
can you give more examples please 

darragh:
20160216 23:59:47
Definitely a tricky problem. The time limit didn't turn out to be an issue for me but I had never actually used branch and bound to solve such a problem so I made a lot of mistakes in my implementation. I'd normally use dynamic programming but the constraints did now allow for it in this case. 

Andy:
20150506 10:03:30
time limit is ~2.5x slowest judge solution 

eightnoteight:
20150505 17:10:41
time limit is outrageous,

Added by:  Andy 
Date:  20150420 
Time limit:  0.100s0.150s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 