配点 : $200$ 点

問題文

$N$ 個の宝石があり、$i$ 番目の宝石の価値は $V_i$ です。

あなたはこれらの宝石の中からいくつかを選んで手に入れます。

このとき、$1$ つも選ばなくとも、全て選んでも構いません。

ただし、$i$ 番目の宝石を手に入れる場合コスト $C_i$ を支払わなければいけません。

手に入れた宝石の価値の合計を $X$、支払ったコストの合計を $Y$ とします。

$X-Y$ の最大値を求めてください。

制約

• 入力は全て整数である。
• $1 \leq N \leq 20$
• $1 \leq C_i, V_i \leq 50$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$V_1$ $V_2$ $...$ $V_N$

$C_1$ $C_2$ $...$ $C_N$

出力

$X-Y$ の最大値を出力せよ。

3
10 2 5
6 3 4

5

$1$ 番目の宝石と $3$ 番目の宝石を選んだとき、$X = 10 + 5 = 15, Y = 6 + 4 = 10$ です。 このとき、$X-Y = 5$ となり、これが最大です。

4
13 21 6 19
11 30 6 15

6

1
1
50

0