Cow Event Assignment with Bonuses

Farmer John's \(N\) cows (\(1 \leq N \leq 20\)), labeled \(1\dots N\), are preparing for an N-athlon with \(N\) different events. Each cow \(i\) has a skill level \(s_{ij}\) (\(1 \leq s_{ij} \leq 1000\)) for event \(j\). Each cow must participate in exactly one event, and each event must have exactly one cow competing.

The team's total score is the sum of the skill levels attained in the events. In addition, there are \(B\) bonus conditions (\(1 \leq B \leq 20\)). Bonus \(i\) is described by three integers: \(K_i, P_i, A_i\), meaning that if the cows accumulate at least \(P_i\) points in the first \(K_i\) events (including any bonuses awarded for those events), then an extra \(A_i\) points will be added to the team's score.

For example, consider \(N = 3\) cows with the following skills:

         Event
         1   2   3
Cow 1:  5   1   7
Cow 2:  2   2   4
Cow 3:  4   2   1

Suppose there is one bonus condition: if the total for the first 2 events is at least 7, add 6 bonus points. One optimal assignment is:

• Cow 1 in event 1 (score 5)
• Cow 3 in event 2 (score 2)
• Cow 2 in event 3 (score 4)

The first 2 events yield \(5+2=7\) points, satisfying the bonus, so an extra 6 points are added. The total score is \(5+2+4+6=17\).
Decide on an assignment of cows to events that maximizes the total score.

inputFormat

The first line contains two integers \(N\) and \(B\) separated by a space.

The next \(N\) lines each contain \(N\) integers. The \(j\)th integer in the \(i\)th line denotes \(s_{ij}\), the skill level of cow \(i\) in event \(j\).

The following \(B\) lines each contain three integers \(K_i\), \(P_i\), and \(A_i\) representing a bonus. Bonus \(i\) is awarded if the total score (including other bonuses) for the first \(K_i\) events is at least \(P_i\). In that case, \(A_i\) points are added.

Note: Events are 1-indexed, and the first \(K\) events refer to events 1 through \(K\) in order.

Example:

3 1
5 1 7
2 2 4
4 2 1
2 7 6

outputFormat

Output a single integer: the maximum total score achievable by optimally assigning cows to events.

Example Output:

17

sample

3 1
5 1 7
2 2 4
4 2 1
2 7 6

17