## Day 2, Problem 1: Computer Purchase Return

The computer that you are going to build is composed of T (1 ≤ T ≤ 5) different types of components. Your computer must have exactly one of each type of component.

Each component has an integer cost ci (1 ≤ ci ≤ 3000), an integer value vi (1 ≤ vi ≤ 3000), and type ti (1 ≤ tiT).

Your on-line computer parts store has N different components (1 ≤ N ≤ 1000) that you can select from.

For a given budget B (1 ≤ B ≤ 3000), maximize the total value of the components in your computer.

If you cannot construct such a computer, you should print -1.

### Input

The first line contains T, the number of types of components your computer requires. The next line contains the number N, followed by N lines of three integers, representing ci, vi, and ti, each separated by one space. The last line of input is the budget B.

### Output

Output the value of the maximum valued computer you can create which costs at most B, or -1 if you cannot construct a computer.

```2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16```

`18`

### Explanation

Notice that picking the components with cost 11 and 5 yields a computer with value 18. No other combination of components has a higher value.

Point Value: 10
Time Limit: 2.00s
Memory Limit: 256M