配点: $100$ 点

問題文

ギガ君は，「GigaCode 20XX」というイベントに参加するために，小遣いからパソコンを購入することになりました．今日を $1$ 日目とすると，彼は $D$ 日目までにパソコンを購入しなければなりません．

$1$ 日目の朝の段階で，彼が持っている小遣いの金額は $0$ 円です．また，$i$ 日目の正午には小遣い $a_i$ 円が彼に渡されます．

さて，パソコンの価格は毎日変動します．$i$ 日目のパソコンの価格は $b_i$ 円であり，この価格はその日の 0 時から 24 時まで変わりません．

$D$ 日間分の小遣いの情報・パソコンの価格の情報が与えられたとき，彼が買うことのできるパソコンの価格としてあり得る最小値を求めてください．ただし，彼がパソコンを $D$ 日目までに購入することができない場合は -1 と出力してください．なお，与えられた小遣い以外の金は使うことができないものとします．

制約

• $1 \\leq D \\leq 200 \\ 000$
• $1 \\leq a_1, a_2, a_3, \\dots, a_D \\leq 200 \\ 000$
• $1 \\leq b_1, b_2, b_3, \\dots, b_D \\leq 2 \\ 000 \\ 000 \\ 000$
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (20 点) $D = 1$ を満たす．
2. (40 点) $D \\leq 365$ を満たす．
3. (40 点) 追加の制約はない．

---

入力

入力は以下の形式で標準入力から与えられます．

$D$ $a_1$ $a_2$ $a_3$ ... $a_D$ $b_1$ $b_2$ $b_3$ ... $b_D$

出力

ギガ君が買うことのできるパソコンの価格としてあり得る最小値を出力してください．
ただし，彼がパソコンを $D$ 日目までに購入することができない場合は -1 と出力してください．

---

入力例 1

1
120000
100000

出力例 1

100000

彼は $1$ 日目の夜の時点で $120 \\ 000$ 円持っているため，$1$ 日目の夜に $100 \\ 000$ 円のパソコンを購入することができます．
よって，100000 と出力するのが正解です．

なお，この入出力例は，小課題 $1$ の制約，小課題 $2$ の制約を満たします．

---

入力例 2

1
70000
100000

出力例 2

-1

彼は $1$ 日目の夜の時点で $70 \\ 000$ 円持っていますが，パソコンを購入するのに $100 \\ 000$ 円かかるため，彼はパソコンを購入することができません．
よって，-1 と出力するのが正解となります．

---

入力例 3

5
10000 10000 10000 10000 10000
41210 27556 29018 42919 33762

出力例 3

29018

彼が $1$ 日目の夜にパソコンを購入しようとした場合：

• 所持金：$10 \\ 000$ 円
• パソコンの価格：$41 \\ 210$ 円 → 購入できない

彼が $3$ 日目の夜にパソコンを購入しようとした場合：

• 所持金：$10 \\ 000 + 10 \\ 000 + 10 \\ 000 = 30 \\ 000$ 円
• パソコンの価格：$29 \\ 018$ 円 → 購入できる

彼が $5$ 日目の夜にパソコンを購入しようとした場合：

• 所持金：$10 \\ 000 + 10 \\ 000 + 10 \\ 000 + 10 \\ 000 + 10 \\ 000 = 50 \\ 000$ 円
• パソコンの価格：$33 \\ 762$ 円 → 購入できる

また，彼は $2, 4$ 日目の夜にパソコンを購入することはできません．よって答えは $29 \\ 018$ 円となります．

なお，この入出力例は，小課題 $2$ の制約を満たします．

---

入力例 4

5
10000 10000 10000 10000 10000
30000 29999 29998 29997 29996

出力例 4

29996