### 2010 Canadian Computing Competition, Stage 2

## Day 2, Problem 1: Computer Purchase Return

After considering to buy a brand new Atari or Commodore computer (based on your extensive research in late February), you decide to get the best value for your dollar by building your own.

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 `c _{i}`
(1 ≤

`c`≤ 3000), an integer value

_{i}`v`(1 ≤

_{i}`v`≤ 3000), and type

_{i}`t`(1 ≤

_{i}`t`≤

_{i}`T`).

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 `c _{i}`,

`v`, and

_{i}`t`, each separated by one space. The last line of input is the budget

_{i}`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.

### Sample Input

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

### Sample Output

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.

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** May 19, 2010

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...