← 返回题目列表

Codeforces · 1519/F

F. 箱子和钥匙

中文机器翻译题面 查看原题

Alice 和 Bob 玩游戏。 Alice 拥有 $$$n$$$ 宝箱(其中第 $$$i$$$ 包含 $$$a_i$$$ 硬币)和 $$$m$$$ 钥匙(她可以将其中 $$$j$$$ 的钥匙以 $$$b_j$$$ 价格卖给鲍勃)。

首先,爱丽丝在箱子上加了一些锁。锁有$$$m$$$种类型,第$$$j$$$种类型的锁只能用第$$$j$$$种钥匙打开。为了在第 $$$i$$$ 个箱子上放置 $$$j$$$ 类型的锁,Alice 必须支付 $$$c_{i,j}$$$ 美元。爱丽丝可以在每个箱子上放置任意数量的不同类型的锁(可能是零)。

然后,鲍勃从爱丽丝那里购买一些钥匙(可能没有,也可能全部)并打开他能打开的每个箱子(如果他拥有该箱子上所有锁的钥匙,他就可以打开该箱子)。鲍勃的利润是打开的箱子中的硬币总数与他从爱丽丝那里购买钥匙所花费的硬币总数之间的差额。如果鲍勃的利润严格为正(大于零),他就赢得了游戏。否则,爱丽丝赢得了比赛。

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 从 Alice 那里购买第 $$$j$$$ 密钥所需花费的币数。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$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$$$。

否则,打印一个整数——无论 Bob 的行为如何,Alice 必须花费的最少美元才能赢得游戏。

示例

输入 #1

2 3
3 3
1 1 4
10 20 100
20 15 80

输出 #1

205

输入 #2

2 3
3 3
2 1 4
10 20 100
20 15 80

输出 #2

110

输入 #3

2 3
3 4
1 1 4
10 20 100
20 15 80

输出 #3

-1

注意

在第一个示例中,Alice 应该在第一个箱子上放置 $$$1$$$ 和 $$$3$$$ 类型的锁,在第二个箱子上放置 $$$2$$$ 和 $$$3$$$ 类型的锁。

在第二个示例中,Alice 应该在第一个箱子上放置 $$$1$$$ 和 $$$2$$$ 类型的锁,并在第二个箱子上放置 $$$3$$$ 类型的锁。