Gold, Food and Power#90
All computer game designers use artificial intelligence concepts to make their programs smarter and more realistic. The designers of a new strategy game, Unholy Identities (UI), have faced a related challenge, especially when designing computer players. In such games, each player (computer or human) possesses resources such as gold, wood, and ore. The player decides when and where to use these resources. For simplicity, let us assume that in UI there is only one type of resource: gold. The main purpose of gold is for military recruitment. In UI, there are several predefined types of military units. Each type has a price (in gold), a food requirement, and a power value.
When a player wants to recruit a unit, they must have at least the required amount of gold (depending on the unit type) and at least the required amount of food. If the player is able to recruit the unit, their army's total power increases by that unit's power. The UI designers want the program to require recruiting exactly a fixed number of units.
Task: Help the UI designers program a computer player who, given a specific amount of gold, food, and an exact number of unit selections, can maximize the total power of their army.
For example, if you have gold, food, and must recruit exactly units, you should choose units so that the total food does not exceed , the total cost does not exceed , and their total power (the sum of their powers) is maximized. Note that you may select the same type of unit more than once.
The first line contains the number of test cases.
Each test case begins with a line containing four integers: the first, (0 \leq M \leq 5000), is the available amount of gold; the second, (0 \leq F \leq 500), is the available amount of food; the third, , is the exact number of units to select; and the fourth, (1 \leq U, T \leq 10), is the number of available unit types.
The next lines describe the unit types. Each line contains three integers: the unit's price (between and ), food requirement (between and ), and power (a non-negative integer). There are no two identical unit types.
For each test case, print a single integer: the maximum total power that can be achieved, or impossible if it is not possible to select the required number of units using the available gold and food.
Example 2