你是I国的一位高级将领，你刚获得了一大笔经费M，你需要使用这笔经费组建一只强大的陆军。陆军有很多种军种，因为军队的战斗力从来不是人越多越强，兵种的战斗力不是线性的，你还需要配置不同类型的兵种，你还需要为他们配置相应的武器装备。求解在给定情况下的最大战斗力。

给定总经费M，兵种种类数量N，每个兵种的单位花费C_i和单位数量x对应的战斗力公式f_i(x)。求总战斗力之和的最大值。

从文件army.in中读入数据。输入的第一行包含 2 个整数m,n。

输入的第二行为n个整数，第i个数表示兵种i的单位花费C_i。

输入的第三行到n+2行，第i+2行表示兵种i的战斗力多项式。每行第一个数字k_i表示多项式有k项,之后有j个数。

每行第a_{j+1}个数是多项式中x^j的系数。表示战斗力的公式为$f_i(x)=a_2\bullet x^1+a3\bullet x^2+...+a{k+1}\bullet x^k$

输出到文件army.out中。输出仅一个数字，表示总战斗力之和的最大值。

总计费用为21。有2种兵种可供选择。第1种单位花费4，战斗力函数为f(x)=2\operatorname{x}^2+2x。第2种单位花费1，战斗力函数为f\left(x\right)=3x。最优方案为第1种为5个单位的数量，第2种单位为1个单位的数量。总费用为2\times5^2+2\times5+3\times1=63。

对于所有测试数据保证：0\leq M\leq {10}^4,1\leN\le100,1\le C_i\le{10}^4,1\leq \operatorname{k}_i\leq 5,1\leq |\operatorname{a}_j|\leq 20。保证结果不超过long long。

原创