No.957 植林

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 22
作問者 : TaprisちゃんTaprisちゃん / テスター : treeonetreeone
2 ProblemId : 3556 / 出題時の順位表
問題文最終更新日: 2019-12-19 16:25:14

問題文

$H$ 行 $W$ 列のマス目があり, それぞれのマスには木を植えることができます。$i$ 行 $j$ 列目のマスに木を植えるとき $G_{i,j}$ 円かかります。

また, $i$ 行目のすべてのマスに木を植えると $R_i$ 円を得ます。 同様に $j$ 列目のすべてのマスに木を植えると $C_j$ 円を得ます。

このとき 収益 の最大値を求めてください。収益 とは, 条件を満たすことで得られた代金の和から, 木を植えるのにかかった代金の和を引いた値と定義します。

入力

$H$ $W$
$G_{1,1}$ $G_{1,2}$ $\cdots$ $G_{1,W}$
$G_{2,1}$ $G_{2,2}$ $\cdots$ $G_{2,W}$
$:$
$G_{H,1}$ $G_{H,2}$ $\cdots$ $G_{H,W}$
$R_1$ $R_2$ $\cdots$ $R_H$
$C_1$ $C_2$ $\cdots$ $C_W$
  • $1 \leq H, W \leq 300$
  • $0 \leq G_{i,j}, R_{i}, C_{j} \leq 10^9$
  • 入力はすべて整数

出力

$1$ 行に答えを出力してください。

サンプル

サンプル1
入力
2 3
1 2 3
4 5 6
6 2
1 7 3
出力
2

$1$ 行目と $2$ 列目のマスに木を植えます。$(6+7)-(1 + 2 + 3 + 5) = 2$ 円となります。

サンプル2
入力
3 1
3
1
4
1 5 9
2
出力
9

すべてのマスに木を植えます。$(1+5+9+2)-(3+1+4) = 9$ 円となります。

サンプル3
入力
1 1
100
50
49
出力
0

木を植えないのが最適です。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。