AT_gigacode_2019_c パソコンの購入

[problemUrl]: https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_c ギガ君は，「GigaCode 20XX」というイベントに参加するために，小遣いからパソコンを購入することになりました．今日を $ 1 $ 日目とすると，彼は $ D $ 日目までにパソコンを購入しなければなりません． $ 1 $ 日目の朝の段階で，彼が持っている小遣いの金額は $ 0 $ 円です．また，$ i $ 日目の正午には小遣い $ a_i $ 円が彼に渡されます． さて，パソコンの価格は毎日変動します．$ i $ 日目のパソコンの価格は $ b_i $ 円であり，この価格はその日の 0 時から 24 時まで変わりません． $ D $ 日間分の小遣いの情報・パソコンの価格の情報が与えられたとき，彼が買うことのできるパソコンの価格としてあり得る最小値を求めてください．ただし，彼がパソコンを $ D $ 日目までに購入することができない場合は `-1` と出力してください．なお，与えられた小遣い以外の金は使うことができないものとします．

入力は以下の形式で標準入力から与えられます． > $ D $ $ a_1 $ $ a_2 $ $ a_3 $ ... $ a_D $ $ b_1 $ $ b_2 $ $ b_3 $ ... $ b_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 点) 追加の制約はない． ### Sample Explanation 1 彼は $ 1 $ 日目の夜の時点で $ 120\ 000 $ 円持っているため，$ 1 $ 日目の夜に $ 100\ 000 $ 円のパソコンを購入することができます． よって，`100000` と出力するのが正解です． なお，この入出力例は，小課題 $ 1 $ の制約，小課題 $ 2 $ の制約を満たします． ### Sample Explanation 2 彼は $ 1 $ 日目の夜の時点で $ 70\ 000 $ 円持っていますが，パソコンを購入するのに $ 100\ 000 $ 円かかるため，彼はパソコンを購入することができません． よって，`-1` と出力するのが正解となります． ### Sample Explanation 3 彼が $ 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 $ の制約を満たします．