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 ~i~th 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 ~i~th 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.
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 one integer, the maximum profit they can have.
3 2 1 2 3 2 3 4 3 4 5 10 5 20 10
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.