UVA10498 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) 搬运