103266: [Atcoder]ABC326 G - Unlock Achievement

Problem Statement

There are $N$ skills numbered $1$ to $N$ and $M$ achievements numbered $1$ to $M$.

Each skill has a positive integer level, and the initial level of every skill is $1$.

You can pay a cost of $C_i$ yen to increase the level of skill $i$ by $1$. You can do this as many times as you want.

Achievement $i$ is achieved when the following condition is satisfied for every $j=1,\ldots,N$, for which you will receive a reward of $A_i$ yen.

• Condition: The level of skill $j$ is at least $L_{i,j}$.

Find the maximum possible total reward obtained minus the total cost required when appropriately choosing how to raise the skill levels.

Constraints

• $1 \leq N,M \leq 50$
• $1 \leq L_{i,j} \leq 5$
• $1 \leq A_i,C_i \leq 10^6$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print the answer as an integer.

Sample Input 1

2 2
10 20
100 50
3 1
1 4

Sample Output 1

80

There are two skills. It costs $10$ yen to raise the level of skill $1$ and $20$ yen to raise the level of skill $2$.
There are two achievements. Achievement $1$ is achieved when skill $1$ is at least level $3$ and skill $2$ is at least level $1$, for which you will receive $100$ yen. Achievement $2$ is achieved when skill $1$ is at least $1$ and skill $2$ is at least level $4$, for which you will receive $50$ yen.

By raising skill $1$ to level $3$ and skill $2$ to level $1$, you will receive the reward of $100$ yen for the cost of $20$ yen, and the balance is $80$ yen.

Sample Input 2

2 2
10 20
100 50
3 2
1 4

Sample Output 2

70

By raising skill $1$ to level $3$ and skill $2$ to level $4$, you will receive the reward of $150$ yen for the cost of $80$ yen, and the balance is $70$ yen.

Sample Input 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

Sample Output 3

66900

问题描述

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

每个技能都有一个正整数等级，初始等级为$1$。

你可以花费$C_i$日元将技能$i$的等级提高$1$。你可以无数次地这样做。

当以下条件对满足$j=1,\ldots,N$的每个$j$都成立时，成就$i$就会达成，你将获得$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

有两个技能。提高技能$1$的等级需要花费$10$日元，提高技能$2$的等级需要花费$20$日元。
有两个成就。 成就$1$是当技能$1$至少达到等级$3$且技能$2$至少达到等级$1$时获得的，你将获得$100$日元的奖励。 成就$2$是当技能$1$至少达到$1$且技能$2$至少达到等级$4$时获得的，你将获得$50$日元的奖励。

通过将技能$1$提高到等级$3$和技能$2$提高到等级$1$，你将以$20$日元的成本获得$100$日元的奖励，余额为$80$日元。

样例输入2

2 2
10 20
100 50
3 2
1 4

样例输出2

70

通过将技能$1$提高到等级$3$和技能$2$提高到等级$4$，你将以$80$日元的成本获得$150$日元的奖励，余额为$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