Happiness

有 $n$ 种食物和 $m$ 个人，你的任务是买一些食物，使得每个人都不会吃撑，且在此前提下尽量多花钱。对于每个人 $i$ 来说，每种食物 $j$ 都有一个系数 $a_{ij}$，表示每单位这种食物为这个人带来的愉快值。每个人 $i$ 还有一个最大愉快值 $b_i$，表示当食物为他带来的总愉快值超过 $b_i$ 时，此人将会吃撑。 **输入格式** 输入包含多组数据。每组数据的第一行为两个整数 $n$ 和 $m$，第二行包括 $n$ 个实数，表示每种食物的单价；以下 $m$ 行每行包含 $n+1$ 个实数，前 $n$ 个实数分别为系数 $a_{i1},a_{i2},...,a_{in}$，最后一个整数为 $b_i$。输入结束标志为 EOF。 **输出格式** 对于每组数据，输出花的钱数的最大值，向上取整。具体格式见样例。 **数据范围** $3 \leq n,m \leq 20$。 **翻译来自 刘汝佳，陈锋《算法竞赛入门经典-训练指南》** @[Fее_cle6418](https://www.luogu.com.cn/user/390770) 搬运

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1439 [PDF](https://uva.onlinejudge.org/external/104/p10498.pdf) 



3 3
1 0.67 1.67
1 2 1 430
3 0 2 460
1 4 0 420

Nasa can spend 1354 taka.