Cow Decathlon

Time limit1sMemory limit128 MB

Summary

Assign each cow to one event to maximize base scores plus prefix bonuses that cascade when thresholds are met.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

Farmer John's $N$ cows ( $1 \le N \le 20$ ), labeled $1$ through $N$ as always, are training for a decathlon with $N$ events. With a number of events other than ten, $N$ -athlon would be the accurate name, but the name stays.

Cow $i$ scores $s_{ij}$ points ( $1 \le s_{ij} \le 1000$ ) in event $j$ . Each cow competes in exactly one event, and each event has exactly one cow in it.

The team's base score is the sum of the skill levels of the events its cows compete in. The judges hand out bonuses on top of that when a performance impresses them. There are $B$ bonuses ( $1 \le B \le 20$ ), and bonus $i$ is given by three integers $K_i$ , $P_i$ , $A_i$ ( $1 \le K_i \le N$ , $1 \le P_i \le 40000$ , $1 \le A_i \le 1000$ ). If the team earns at least $P_i$ points over the first $K_i$ events, it receives $A_i$ more points.

The points earned over the first $K_i$ events include bonuses already awarded for those same events, so if bonus $j$ with $K_j \le K_i$ has been awarded, its $A_j$ counts too. Bonuses are settled in increasing order of $K$ . When several bonuses share the same $K$ , keep awarding any bonus whose threshold is met until none is left that qualifies. No bonus is awarded twice.

For example, take $N = 3$ cows with these skill levels.

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

Cow 1 earns the team 7 points if she competes in event 3. Say there is one bonus, worth 6 extra points if the cows score at least 7 points over the first two events. The best assignment sends cow 1 to event 1, cow 2 to event 3, and cow 3 to event 2. Over the first two events cow 1 scores 5 and cow 3 scores 2, which meets the threshold of 7. The total is $5 + 2 + 4 + 6 = 17$ points.

Assign the cows to events so that the total score is as large as possible.

Input

The first line holds the number of cows and events $N$ and the number of bonuses $B$ , separated by a space.

Each of the next $B$ lines describes one bonus. Line $i$ of this block holds $K_i$ , $P_i$ , $A_i$ , separated by spaces.

Each of the next $N$ lines holds the skill levels of one cow. Line $j$ of this block holds $s_{j1}, s_{j2}, \dots, s_{jN}$ , the points cow $j$ scores in each event, separated by spaces.

Output

Print the largest total score the cows can reach, bonuses included.

Examples2

Example 1
Input
```
3 1
2 7 6
5 1 7
2 2 4
4 2 1
```
Expected output
```
17
```
Example 2
Input
```
2 2
1 12 3
1 10 5
10 1
5 20
```
Expected output
```
38
```