Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 1
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
Each component has an integer cost
Your online computer parts store has
For a given budget
If you cannot construct such a computer, you should print -1
.
Input Specification
The first line contains
Output Specification
Output the value of the maximum valued computer you can create which costs at most -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
Comments