475. Be a Smart Raftsman
Time limit per test: 1.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
On Halloween, when other people are gathering to tell terrifying stories (see problem H. "Hero of our time"), to torment poor pumpkins (see problem J. "Jealous Cucumber"), to create demonic teams (see problem C. "Coach's Trouble"), in other words, to do all that stuff, you don't want to be ordinary, so now you are planning to try some extreme sports. Rafting would be the best choise, because when water is cold enough (as it is now!) rafting is extremely extreme.
You are members of a rafting crew which consists of
n participants. You navigate the river, and your goal is to pass
m consecutive riffles and to get from the start to the finish as soon as possible. The
ith riffle is characterized by critical weight
c_{i}, and the
jth participant is characterized by his or her weight
w_{j}. If your raft goes through the
ith riffle with people on board with total weight exceeding
c_{i}, it capsizes. This part of rafting is the most exciting, but it requires additional time to get on the raft after capsize. So sometimes it is better to take a group of people with total weight not exceeding critical weight on the raft, while others pass the distance by foot.
More formally, consider
m + 1 points
p_{0},
p_{1},...,
p_{m}, where
p_{0} is the start and
p_{m} is the finish. Each of the intermediate points
p_{i} (1 ≤
i ≤
m1) is located between the
ith and (
i + 1)th riffle. It takes
D_{i} minutes for the raft to get from
p_{i1} to
p_{i}, if it passes the
ith riffle with capsize, and
d_{i} minutes otherwise. The
jth participant can get from
p_{i1} to
p_{i} in
t_{j} minutes by foot. It takes him or her
s_{j} minutes to get on the raft or to get off the raft on the bank. Before each of the riffles your group is divided into two parts. The first part rafts through the riffle (with or without capsize), and the second part goes on the bank to the next intermediate point. At this point they always wait for the raft, or the raft waits for all the walkers, if it arrives sooner. Then some participants who are on the raft can get off, and some participants who are on the bank can get on the raft. They can't start doing it before the raft and all the walkers arrive to the point. The total time required for this action is equal to the sum of
s_{j} for people changing their place. Then you pass the next riffle and so on, until you get to the finish. Note that no one can start moving to the next point until others have changed places.
Remember, that you start at the point
p_{0} having all your group on the bank (not on the raft), and you must finish at the point
p_{m} also with all participants on the bank and the raft with you. You are not allowed to leave the raft at the start or at some intermediate point, and walk to the finish without it. You can take all the group to the raft to pass a riffle, but you can't leave the raft empty during the trip. Your task is to calculate the minimal time required to reach the finish.
Input
The first line of the input contains two numbers
n and
m (1 ≤
n ≤ 10, 1 ≤
m ≤ 1000). Following
n lines describe participants. Each of them consists of three integers
w_{j},
t_{j},
s_{j}. Following
m lines also contains three integers each —
c_{i},
D_{i} and
d_{i} for the
ith riffle. All numbers in the input are positive integers not exceeding 10000.
Output
Output the minimal time.
Example(s)
sample input

sample output

2 3
50 5 1
70 20 1
30 15 10
60 100 10
70 100 10

51

Note
Consider an optimal strategy for the example:
both participants get on the raft (2 minutes), they pass the first riffle with capsize (15 minutes), second participant gets off (1 minute), first participant raft through the riffle, while his mate walks ( minutes), they swap places (2 minutes), they get to the finish — first one by foot, second one by raft (), second participant gets off (1 minute).