## A Knapsack Problem

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M
Authors:

Problem types

Roger and George run a transport company.

One day their boss Victor tells them to transport some subset of the goods to another warehouse. Roger observes that there are of the th item, each taking up volume in their truck, and will give them a profit of each.

George is looking at the trucks, and observes that there are of these trucks. The th truck has a capacity of , but will cost dollars for refueling. They must drive exactly one truck.

Can you help them maximize their profit?

#### Input Specification

The first line contains two integers, .
The next lines contain three integers, .
The next lines contain two integers, .

#### Output Specification

Output one integer, the maximum profit they can have.

#### Sample Input

3 2
1 2 3
2 3 4
3 4 5
10 5
20 10

#### Sample Output

16

#### Explanation for Sample Output

Roger and George can get a profit of 26 from transporting the items, but must pay 10 for their truck.

#### Sample Input 2

4 1
1 10 10
1 9 10
2 8 10
10 2 10
1 10

#### Sample Output 2

-10

#### Explanation for Sample Output 2

There is only one type of truck available in this case, and unfortunately none of the items can fit in this truck. Because Roger and George aren't very smart, they must drive a truck even if they would make more profit not driving a truck.