CF1519F Chests and Keys

Alice 和 Bob 玩一个游戏。Alice 有 $n$ 个宝箱（第 $i$ 个宝箱里有 $a_i$ 枚金币），还有 $m$ 把钥匙（第 $j$ 把钥匙可以卖给 Bob，售价为 $b_j$ 枚金币）。 首先，Alice 会在宝箱上加锁。有 $m$ 种类型的锁，第 $j$ 种类型的锁只能用第 $j$ 把钥匙打开。若要在第 $i$ 个宝箱上加第 $j$ 种类型的锁，Alice 需要花费 $c_{i,j}$ 美元。每个宝箱可以加任意数量的不同类型的锁（也可以一个都不加）。 接着，Bob 可以从 Alice 那里购买任意数量的钥匙（可以一把都不买，也可以全部买下），然后打开他能打开的宝箱（如果他拥有打开该宝箱所有锁的钥匙，则可以打开该宝箱）。Bob 的收益等于他打开的所有宝箱中的金币总数减去他购买钥匙所花费的金币总数。如果 Bob 的收益严格大于零（即收益为正），则他赢得游戏。否则，Alice 获胜。 Alice 想要在一些宝箱上加锁，使得无论 Bob 购买哪些钥匙，她都能获胜（即 Bob 无法获得正收益）。当然，她希望花在加锁上的美元数尽可能少。请你帮她判断是否有可能获胜，如果可以，最少需要花费多少美元加锁。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 6$），分别表示宝箱和钥匙的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 4$），其中 $a_i$ 表示第 $i$ 个宝箱中的金币数。 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_j \le 4$），其中 $b_j$ 表示 Bob 购买第 $j$ 把钥匙需要花费的金币数。 接下来 $n$ 行，每行 $m$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,m}$（$1 \le c_{i,j} \le 10^7$），其中 $c_{i,j}$ 表示 Alice 在第 $i$ 个宝箱上加第 $j$ 种类型的锁需要花费的美元数。

如果 Alice 无法确保获胜（无论如何加锁，Bob 总有办法获得正收益），输出 $-1$。 否则，输出一个整数，表示 Alice 至少需要花费多少美元加锁，才能保证无论 Bob 如何选择钥匙，她都能获胜。

在第一个样例中，Alice 应该在第一个宝箱上加第 $1$ 和第 $3$ 种锁，在第二个宝箱上加第 $2$ 和第 $3$ 种锁。 在第二个样例中，Alice 应该在第一个宝箱上加第 $1$ 和第 $2$ 种锁，在第二个宝箱上加第 $3$ 种锁。 由 ChatGPT 4.1 翻译