CPU 팔기

CPU 공장에 취직했다. 한 달을 꼬박 일한 대가로 회사는 현금 대신 똑같은 CPU $c$개를 주었다. 지금 회사에 현금이 없다고 한다.

CPU만 먹고 살 수는 없으니 시장에 나가 CPU를 팔고 그 돈으로 생활에 필요한 것을 사려고 한다. 그런데 이 시장은 거래 방식이 엄격하다. 시장에는 한 번만 들어갈 수 있고, 상인 한 명과는 한 번만 거래할 수 있으며, 정해진 순서대로 상인을 찾아가야 한다. 시장 운영진이 상인에게 $1$번부터 $m$번까지 번호를 붙여 두었고, 이 번호 순서대로 방문해야 한다. 상인마다 CPU 개수별로 쳐 주는 값이 다르다.

한 상인 앞에서는 아무것도 팔지 않고 지나갈 수도 있고, 아직 손에 남은 CPU 중 몇 개를 골라 한 번에 팔 수도 있다.

첫째 줄에 CPU의 개수 $c$와 상인의 수 $m$이 주어진다 ($1 \le c, m \le 100$).

다음 $m$개의 줄에 $1$번 상인부터 $m$번 상인까지 차례대로 상인의 정보가 주어진다. 각 줄에는 $c$개의 정수 $p_1, \dots, p_c$가 주어지며, $p_i$는 그 상인이 CPU $i$개를 사면서 지불하는 금액이다 ($1 \le p_i \le 10^5$).

가지고 있는 CPU를 팔아서 벌 수 있는 최대 금액을 출력한다.

CPU를 전부 팔지 않아도 된다.