题目描述

小王参加的考试是几门科目的试卷放在一起考，一共给$\red{t}$分钟来做。他现在已经知道每门科目花的时间和得到的分数的关系，还有写名字要的时间（他写自己的名字很慢）请帮他算一下他最高能得几分。总分一定时，第一门科目成绩尽量高，第一门科目成绩也一样时，第二门科目成绩尽量高…………以次类推。如果放弃某一门的考试（花的时间为$\red{0）}$，那么名字也就不用写了。

输入格式

第一行二个正整数$\red{t，}$$\red{n，}$$\red{name. t}$是总时间，$\red{n}$表示考$\red{n}$个科目，$\red{name}$表示写名字要的时间（每一门科目写名字时间一样）。

接下来 $\red{n}$行，每行$\red{n}$ 个正整数，第$\red{i}$个数表示时间为$\red{i}$时这门科目的分数（不一定递增）。时间为$\red{0}$时这门科目的分数为$\red{0，}$所以就不读入了。

输出格式

一个数，即总分。

样例

输入样例

5 3 1
1 2 3 4 5             
2 3 3 4 6
3 3 3 2 5

输出样例

6