Unlock Achievement

题目描述

有 $N$ 个技能，编号为 $1$ 到 $N$，以及 $M$ 个成就，编号为 $1$ 到 $M$。 每个技能都有一个正整数等级，且每个技能的初始等级为 $1$。 你可以支付费用 $C_i$ 日元使技能 $i$ 的等级增加 $1$。你可以无数次地这样做。 当以下条件对于每个 $j=1,\ldots,N$ 成立时，你将获得成就 $i$ 并得到 $A_i$ 日元的奖励。

条件：技能 $j$ 的等级至少为 $L_{i,j}$。

当适当地选择如何提高技能等级时，求可以获得的总奖励减去总花费的最大可能值。

输入格式

输入按下列格式从标准输入给出： $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}$

输出格式

以整数形式输出答案。

2 2
10 20
100 50
3 1
1 4

80

2 2
10 20
100 50
3 2
1 4

70

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

66900

提示

$1 \leq N,M \leq 50$ $1 \leq L_{i,j} \leq 5$ $1 \leq A_i,C_i \leq 10^6$ 所有输入值均为整数。有两个技能。将技能 $1$ 提高一级需要花费 $10$ 日元， 将技能 $2$ 提高一级需要花费 $20$ 日元。
有两个成就。 成就 $1$ 在技能 $1$ 至少达到等级 $3$ 且技能 $2$ 至少达到等级 $1$ 时达成，达成可得到 $100$ 日元的奖励。 成就 $2$ 在技能 $1$ 至少达到等级 $1$ 且技能 $2$ 至少达到等级 $4$ 时达成，达成可得到 $50$ 日元的奖励。 将技能 $1$ 提升到等级 $3$ 且技能 $2$ 保持在等级 $1$，你将以 $20$ 日元的花费获得 $100$ 日元的奖励，余额为 $80$ 日元。
将技能 $1$ 提升到等级 $3$ 且技能 $2$ 提升到等级 $4$，你将以 $80$ 日元的花费获得 $150$ 日元的奖励，余额为 $70$ 日元。

标签: AtCoder|abc326G

来源

AtCoder|abc326G