Maximizing National Profit through Equipment Allocation

The head company owns $M$ high-performance devices and plans to distribute them among $N$ branch companies. Each branch generates a certain profit when allocated some devices. If a branch is given $j$ devices (with $j\ge0$, and the profit for $0$ devices is $0$), it will yield a profit which is provided as input. Determine the maximum total profit that can be obtained by distributing at most $M$ devices among the $N$ branches.

The allocation follows these rules:

• Each branch can be allocated any number of devices (including zero).
• The sum of devices allocated to all branches must not exceed $M$.

Constraints: $M\le15$, $N\le10$.

inputFormat

The input begins with a line containing two integers $M$ and $N$, where $M$ is the total number of devices and $N$ is the number of branch companies.

This is followed by $N$ lines. The i-th of these lines contains $M$ space-separated integers. The $j$-th integer on this line (for $1 \le j \le M$) represents the profit obtained if the i-th branch is allocated exactly $j$ devices. It is assumed that allocating $0$ devices yields a profit of $0$.

outputFormat

Output a single integer representing the maximum profit that can be achieved by optimally distributing the devices.

sample

5 3
3 5 8 9 10
2 3 4 8 9
1 4 6 7 8

12