← 返回题目列表

AtCoder · abc326_g

G. 解锁成就

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

分数: 625 点

问题陈述

有 N 技能编号 1 to N 和 M 成就屈指可数 1 to M.

每个技能都有一个正整数等级,每个技能的初始等级为 1.

您可以支付以下费用 C_i 日元提高技能等级 i by 1。您可以根据需要多次执行此操作。

成就 当每个满足以下条件时,即可实现 i 当每个满足以下条件时实现 j=1,\ldots,N,为此您将获得奖励 A_i 日元。

  • 条件:技能水平 j 至少 L_{i,j}.

在适当选择如何提高技能水平时,找到最大可能获得的总奖励减去所需的总成本。

约束

  • 1 \leq N,M \leq 50
  • 1 \leq L_{i,j} \leq 5
  • 1 \leq A_i,C_i \leq 10^6
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
C_1 \ldots C_N
A_1 \ldots A_M
L_{1,1} \ldots L_{1,N}
\vdots
L_{M,1} \ldots L_{M,N}

输出

将答案打印为整数。


示例输入 1

2 2
10 20
100 50
3 1
1 4

示例输出 1

80

有两个技能。它的成本 10 日元提高技能水平 1 和 20 日元提高技能水平 2.
有两项成就。 成就 当技能达到 1 当技能达到时 1 至少达到等级 3 和技能 2 至少达到等级 1,您将收到 100 日元。 成就 2 当技能达到时 1 至少 1 和技能 2 至少达到等级 4,您将收到 50 日元。

通过提高技能 1 达到水平 3 和技能 2 达到水平 1,您将获得奖励 100 日元的成本 20 日元,余额为 80 日元。


示例输入 2

2 2
10 20
100 50
3 2
1 4

示例输出 2

70

通过提高技能 1 达到水平 3 和技能 2 达到水平 4,您将获得奖励 150 日元的成本 80 日元,余额为 70 日元。


示例输入 3

10 10
10922 23173 32300 22555 29525 16786 3135 17046 11245 20310
177874 168698 202247 31339 10336 14825 56835 6497 12440 110702
2 1 4 1 3 4 4 5 1 4
2 3 4 4 5 3 5 5 2 3
2 3 5 1 4 2 2 2 2 5
3 5 5 3 5 2 2 1 5 4
3 1 1 4 4 1 1 5 3 1
1 2 3 2 4 2 4 3 3 1
4 4 4 2 5 1 4 2 2 2
5 3 1 2 3 4 2 5 2 2
5 4 3 4 3 1 5 1 5 4
2 3 2 5 2 3 1 2 2 4

示例输出 3

66900