题目描述
大聪明准备去郊游，现在他正在准备零食。已知大聪明有一个容积为t的大书包，同时有n*n袋零食，每一种零食都有一定的体积v和可以为大聪明提供的能量w。而这些零食按照属性可以分为n组（例如薯片类，糖果类），每一组有n种零食。大聪明在每一组内最多可以带1袋零食。现在大聪明想知道在不超过书包容积的前提下，他所携带的零食可以提供的最大能量是多少。
输入
第一行为两个整数m,n(1<=m<=100,2<=n<=10),表示书包的容积为m，同时有n组零食，每组有n袋零食。
接下来n*n行，前1~n行为第一组，n+1~2*n为第二组，以此类推。每一行有2个整数，分别表示这袋零食所占的体积v，可以为大聪明提供的能量w。
输出
一个整数，表示可以为大聪明提供的最大能量
样例输入
45 2
10 10
10 5
50 400
30 20样例输出
30提示
【样例说明】
第一组样例数据表示大聪明的书包容积为45，同时有两组零食，每组零食有两袋，第一组第一件零食体积为10，可以为大聪明提供的能量为10，第一组第二件零食体积为10，可以为大聪明提供的能量为10。第二组第一件零食体积为50，可以为大聪明提供的能量为400，第二组第二件零食体积为30，可以为大聪明提供的能量为20，我们选择第一组体积为10，可以为大聪明提供能量为5的零食，和第二组体积为30，可以为大聪明提供能量为20的零食。总体积为40，可以为大聪明提供的能量为30。
