Farmer John's N cows (1 <= N <= 20), conveniently labeled 1...N, are preparing for a decathlon that has N different events.

Cow i has a skill level of s_ij (1 <= s_ij <= 1000) when competing in event j. Each cow must compete in one and only one event, and each event must have some cow competing in it.

The total score for all cows is the sum of their skill levels for the events in which they are competing. However, the event judges can also give out bonus points. There are B bonuses (1 <= B <= 20). Bonus i has three parts: if the cows obtain at least P_i points (1 <= P_i <= 40,000) for the first K_i events (including other bonuses involving just those events), they will get an additional A_i points (1 <= A_i <= 1000).

Please help decide which events the cows should attempt to maximize their total score.

Line 1: Two space-separated integers: N, B

Lines 2..B+1: Line i+1 will contain the information for bonus i: three space-separated integers K_i, P_i, A_i.

Lines B+2..B+N+1: Line B+1+j will contain N space-separated integers s_j1...s_jN describing how cow j performs at each event.

The maximum amount of points that the cows can receive, including bonuses.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > February > Gold