eolymp
bolt
Try our new interface for solving problems
Problems

Gold, Food and Power

Gold, Food and Power

Time limit 1 second
Memory limit 64 MiB

All computer game designers try to make use of artificial intelligence concepts to make their programs more smart and natural. Designers of a new strategic game, Unholy Identities (UI), have encountered similar needs in their software design especially in designing computer players. In such games each player (computer or human player) has some resources like gold, wood, ore at any time and he (the player) decides when and where to spend these resources. For simplicity, we assume there is only one resource type, i.e. gold in UI. One of the most important fields to spend money is military field. In UI, there are some predefined types of military units. Each type has an associated price, food and power.

When a player wants to recruit a unit, he must have the necessary money determined by type of that unit and also must support the required food. If he can recruit the unit, his total army power is increase by the power of that unit type. UI designers want to make their program, recruit only a fixed number of units.

The problem is to help UI designers to program a computer player such that he (computer player) maximizes his army power when he has specified money and food and fixed number of selections.

For example if we have 300 gold and our food support is 20 and number of unit selection is 3, then we must purchase exactly 3 units such that their total needed food dose not exceed 20 (less than or equal), their total cost dose not exceed 300 (less than or equal) and total power (sum of unit powers) is maximized. Note that one type can be selected more than once.

Input data

The first line of input contains a single integer, the number of test cases. Following, are the data for test cases. Each test case begins with one line which contains four integer numbers. First number, M (0M5000), is the current gold (money) available, second is F (0F500), the food currently available, third is U, the number of unit selection that must exactly be purchased and forth is T, the number of unit types available (1U, T10). Next T lines are data for unit types, one line for each type. Each of these lines has three integers which are unit price (between 1 and 100), unit required food (between 1 and 20) and unit power (non-negative integer). You can assume that no two types are exactly the same.

Output data

There should be one line for each test case that contains a single integer which is the maximum power that can be obtained or the phrase "impossible" if there is no selection set that satisfies both money and food requirements.

Examples

Input example #2
2
300 20 3 3
70 4 280
1 11 22
1 18 300
12 7 2 2
5 4 9
8 2 13
Output example #2
840
impossible