Selling CPUs

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.

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.

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

You do not have to sell all of them.