AT_abc326_g.[ABC326G] Unlock Achievement

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $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
```
2 2
10 20
100 50
3 1
1 4
```
输出#1
```
80
```
输入#2
```
2 2
10 20
100 50
3 2
1 4
```
输出#2
```
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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页