To assemble a computer, you need T components of various types (video card, hard drive, monitor, etc.). The store sells N components. Each component is of a specific type and has a certain cost and rating in magazine reviews.
Write a program that determines which components you need to assemble a computer so that its cost does not exceed B, it contains one component of each type, and the total rating of the components used is maximum.
The first input line contains a single integer – number of component types T (1 ≤ T ≤ 5). The second input line contains a single integer – the number of components in the store N (1 ≤ N ≤ 1000). This is followed by N lines containing three space-separated integers – the cost of the i-th component Ci (1 ≤ Ci ≤ 3000), its rating Ri (1 ≤ Ri ≤ 3000) and its type ti (1 ≤ ti ≤ T). This is followed by a line containing a single integer – budget to buy computer B (1 ≤ B ≤ 3000).
Output in the first line a single integer – the maximum total rating of the used components. In the second line print T integers – The i-th number indicates the number of the i-type component selected for assembly. If there are several options with the maximum total rating, then output the option with the minimum cost from them, and any of these options can be displayed. If there is no option to build a computer within the specified budget, then print a single number –1
in the first line
|
Enter |
Output |
|
2
5
10 6 1
|
18
25 |