AT_abc326_g [ABC326G] Unlock Achievement

题目描述

有 $N$ 种编号为 $1$ 到 $N$ 的技能，以及 $M$ 种编号为 $1$ 到 $M$ 的成就。

每个技能都有一个正整数等级，最初所有技能的等级都是 $1$。

你可以支付 $C_i$ 日元，将技能 $i$ 的等级提升 $1$。这个操作可以进行任意多次。

如果对于成就 $i$，对于所有 $j=1,\ldots,N$，都满足以下条件，则可以达成该成就并获得 $A_i$ 日元的奖励：

• 条件：技能 $j$ 的等级不小于 $L_{i,j}$

请你选择合适的方式提升技能等级，使得获得的奖励总和减去所需总花费的值最大。输出这个最大值。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$C_1$ $C_2$ $\ldots$ $C_N$
$A_1$ $A_2$ $\ldots$ $A_M$
$L_{1,1}$ $L_{1,2}$ $\ldots$ $L_{1,N}$
$\vdots$
$L_{M,1}$ $L_{M,2}$ $\ldots$ $L_{M,N}$

输出格式

请输出一个整数，表示最大化奖励总和减去总花费的最大值。

输入输出样例 #1

输入 #1

2 2
10 20
100 50
3 1
1 4

输出 #1

80

输入输出样例 #2

输入 #2

2 2
10 20
100 50
3 2
1 4

输出 #2

70

输入输出样例 #3

输入 #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

说明/提示

限制条件

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

样例解释 1

有 $2$ 种技能。技能 $1$ 升级需要 $10$ 日元，技能 $2$ 升级需要 $20$ 日元。有 $2$ 种成就。成就 $1$ 需要“技能 $1$ 达到等级 $3$ 且技能 $2$ 达到等级 $1$”，达成后可获得 $100$ 日元。成就 $2$ 需要“技能 $1$ 达到等级 $1$ 且技能 $2$ 达到等级 $4$”，达成后可获得 $50$ 日元。将技能 $1$ 升到 $3$ 级，技能 $2$ 保持 $1$ 级，可以获得 $100$ 日元奖励，花费 $20$ 日元，差值为 $80$ 日元。

样例解释 2

将技能 $1$ 升到 $3$ 级，技能 $2$ 升到 $4$ 级，可以获得 $150$ 日元奖励，花费 $80$ 日元，差值为 $70$ 日元。

由 ChatGPT 4.1 翻译