G - Unlock Achievement 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 625 点

問題文

1 から N の番号がついた N 種類のスキルと、1 から M の番号がついた M 種類のアチーブメントがあります。

各スキルには正整数のレベルが定まっており、最初全てのスキルのレベルは 1 です。

C_i 円のコストを払うことでスキル i のレベルを 1 上げることができます。これは何度でも行なえます。

アチーブメント i は、j=1,\ldots,N の全てについて以下の条件を満たすと達成となり、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

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

2 2
10 20
100 50
3 2
1 4

出力例 2

70

スキル 1 をレベル 3 に、スキル 2 をレベル 4 にすることで、報酬が 150 円、コストが 80 円となり、その差は 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

Score : 625 points

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