A Knapsack Problem

View as PDF

Submit solution

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

Problem types

Roger and George run a transport company.

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

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

Can you help them maximize their profit?


For all subtasks:
1 \le N, M, c_i \le 5000
1 \le n_i, p_i, v_i, f_i \le 10^9

Subtask 1 [5%]

1 \le N, M, n_i, p_i, v_i, c_i, f_i \le 10

Subtask 2 [5%]

1 \le N, M \le 100

Subtask 3 [90%]

No additional constraints.

Input Specification

The first line contains two integers, N, M.
The next N lines contain three integers, n_i, v_i, p_i.
The next M lines contain two integers, c_i, f_i.

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


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


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.


There are no comments at the moment.