Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (20 点) D = 1 を満たす.
- (40 点) D \leq 365 を満たす.
- (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