3289：钓鱼王
时间限制：5 S / 内存限制：65536 KB
AC：77 / Submit：211
| 问题描述 |
|---|
众所周知，原神2.1版本新加了钓鱼系统。玩家可以用鱼换取各种武器和道具。 而非酋ovo小保底歪了七七（guna），大保底才出雷神。他已经没有原石给老婆买武器了。 于是他想要用钓鱼的方式换取一把四星武器，“渔获”。
但每位玩家的鱼是有限的，需要三天时间才会刷新一次，所以很多急于求成的玩家选择去好友的世界里“借”鱼，ovo也是其中的一员。但ovo追求的是“高效”，他想要知道自己一天时间最少的只需要拜访多少位好友就能达成目标。
假设ovo有三个好友，他需要ABC三种鱼，那么他可以选择第 1、3 号或者 2、3 号好友来达成自己的目标，最少只需要拜访 2 位好友。
|
| 输入描述 |
第一行为两个整数 n、m ，表示好友数和鱼的种数。 第二行为 m 个整数 ai，表示ovo对第 i 种鱼的需求量。 从第三行到第 n+2 行，每行m个整数 bij ，表示第 i 为好友拥有第 j 种鱼的数量。 |
| 输出描述 |
一行数字，表示最少需要拜访的好友数量，若无解（拜访所有好友都无法凑齐）则输出QAQ。 输出完后需要换行。 |
| 样例输入复制样例 |
3 3 6 20 20 3 5 15 3 10 15 3 15 5 |
| 样例输出 |
2 |
| 提示说明 |
对于30%的数据，m=1。 对于60%的数据，m=2，0 <= ai,bij <= 10000。 对于100%的数据，1 <= n,m <= 20 ， 0 <= ai,bij <= 2e9。 |
| 相关 |
