Computer Purchase Return

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$.

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$.

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

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.