你是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+a_3\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\leq N\le100,1\le C_i\le{10}^4,1\leq \operatorname{k}_i\leq 5,1\leq |\operatorname{a}_j|\leq 20$。保证结果不超过long long。