Selling CPUs

Interview

Time limit2sMemory limit512 MB

Summary

Sell up to c CPUs across m ordered merchants, each paying p_i for exactly i CPUs in one deal, to maximize total money.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

You got a job at a CPU factory. After a hard month of labor your boss paid you with $c$ identical CPUs instead of cash, because the company is short on money right now.

You cannot live on CPUs alone, so you want to sell them at the market and buy what you need with the proceeds. The market is strict about how you may do business. You may enter the market once, you may trade with each merchant only once, and you have to visit the merchants in a fixed order. The organizers numbered the merchants from $1$ to $m$ , and you must visit them in that order. Every merchant has his own price for each quantity of CPUs.

At a merchant you can walk past without selling anything, or you can sell some of the CPUs you still hold in a single deal.

Input

The first line has two integers $c$ and $m$ ( $1 \le c, m \le 100$ ), the number of CPUs and the number of merchants.

Each of the next $m$ lines describes one merchant, in order from merchant $1$ to merchant $m$ . Such a line has $c$ integers $p_1, \dots, p_c$ ( $1 \le p_i \le 10^5$ ), where $p_i$ is the amount of money that merchant pays for $i$ CPUs.

Output

Print the maximum amount of money you can make by selling the CPUs you have.

You do not have to sell all of them.

Examples2

Example 1
Input
```
5 3
1 4 10 1 1
1 1 8 1 1
1 1 9 1 1
```
Expected output
```
13
```
Example 2
Input
```
1 1
7
```
Expected output
```
7
```