解锁成就

题目描述

有编号 $1$ 到 $N$ 的 $N$ 个技能,以及编号 $1$ 到 $M$ 的 $M$ 个成就。

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

支付 $C_i$ 日元可以将技能 $i$ 的等级提高 $1$。该操作可以任意多次进行。

当满足以下条件时,成就 $i$ 达成,并会获得 $A_i$ 日元奖励。

条件:对于每个 $j=1,\ldots,N$,技能 $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

有两个技能。将技能 $1$ 的等级提高 $1$ 需要花费 $10$ 日元,将技能 $2$ 的等级提高 $1$ 需要花费 $20$ 日元。

有两个成就。 当技能 $1$ 达到至少 $3$ 级、技能 $2$ 达到至少 $1$ 级时,成就 $1$ 达成,获得 $100$ 日元。 当技能 $1$ 达到至少 $1$ 级、技能 $2$ 达到至少 $4$ 级时,成就 $2$ 达成,获得 $50$ 日元。

将技能 $1$ 提升到 $3$ 级、技能 $2$ 提升到 $1$ 级,花费 $20$ 日元获得 $100$ 日元奖励,余额为 $80$ 日元。

2 2
10 20
100 50
3 2
1 4

70

将技能 $1$ 提升到 $3$ 级、技能 $2$ 提升到 $4$ 级,花费 $80$ 日元获得 $150$ 日元奖励,余额为 $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 \le N,M \le 50$
• $1 \le L_{i,j} \le 5$
• $1 \le A_i,C_i \le 10^6$
• 所有输入值均为整数。