## CCO '10 P4 - Computer Purchase Return

View as PDF

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type
##### Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 1

The computer that you are going to build is composed of different types of components. Your computer must have exactly one of each type of component.

Each component has an integer cost , an integer value , and type .

Your on-line computer parts store has different components that you can select from.

For a given budget , maximize the total value of the components in your computer.

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

#### Input Specification

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

#### Output Specification

Output the value of the maximum valued computer you can create which costs at most , 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 for Sample Output

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