Computer Purchase Return

Interview

Time limit2sMemory limit512 MB

Summary

Choose exactly one component of each of T types so the total cost stays within budget B and the total value is maximized.

Level: Medium6 of 10
Topics: Dynamic programming, Array, Implementation, Brute force
Solved: No attempts yet

Problem

You want to build your own computer to get the best value. The computer is made of $T$ ( $1 \le T \le 5$ ) different types of components, and it must contain exactly one component of each type.

Each component has an integer cost $c_i$ ( $1 \le c_i \le 3000$ ), an integer value $v_i$ ( $1 \le v_i \le 3000$ ), and a type $t_i$ ( $1 \le t_i \le T$ ).

An online parts store offers $N$ different components ( $1 \le N \le 1000$ ) to choose from.

For a given budget $B$ ( $1 \le B \le 3000$ ), maximize the total value of the components in your computer while keeping the total cost at most $B$ .

If you cannot build such a computer, print $-1$ .

Input

The first line contains $T$ , the number of component types your computer requires.

The next line contains $N$ . Then $N$ lines follow, each containing three integers $c_i$ , $v_i$ , and $t_i$ separated by single spaces.

The last line contains the budget $B$ .

Output

Print the maximum total value of a computer whose total cost is at most $B$ . If no valid computer can be built, print $-1$ .

Hint

For the sample, choosing the components with cost $11$ and cost $5$ gives a computer with value $18$ , and no other combination reaches a higher value.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
3
3 5 1
2 4 1
10 20 1
5
```
Expected output
```
5
```
Example 3
Input
```
2
2
10 5 1
10 5 2
15
```
Expected output
```
-1
```