22451번 - Air Pollution 다국어

20XX年, ICPC (Ikuta's Computer Pollutes Community) 商店街の経営者たちは大気汚染に悩まされていた。 かつての活気を取り戻すためにも大気の綺麗さを一定以上にしなければならない。

商店街の店は一列に並んでおり、1から$n$で番号付けられている。 現在、おのおのの店のまわりの大気の綺麗さは $p_{i}$ である。 あなたは2から$n-1$番目の店を選んで、その周辺の大気を循環させることで, その店と周囲の店の大気の綺麗さを変更することができる。 正確にいうと, $i$ ( $2 \leq i \leq n-1$ )番目を選んだとき、$p_{i-1}$と$p_{i+1}$には$p_{i}$だけ加算され, 逆に$p_{i}$には$2p_{i}$だけ減算される。つまり、新しい大気の綺麗さ$p'$は,

• $ p'_{i-1} = p_{i-1} + p_{i} $

• $ p'_{i} = p_{i} - 2 p_{i} $

• $ p'_{i+1} = p_{i+1} + p_{i} $ となる。 この操作を繰り返して、すべての店の大気の綺麗さ$p_{i}$を、許容できる最低限の大気の綺麗さ $ l_{i} $ 以上にすることが目的である。

大気を循環させるためには多大な費用がかかるため、なるべく少ない回数で達成したい。 ICPC商店街の未来のためにも力を貸してほしい。

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

$n$

$p_{1}$ ... $p_{n}$

$l_{1}$ ... $l_{n}$

$n$は店の数、$p_{i}$は$i$番目の店の現在の大気の綺麗さ、$l_{i}$は$i$番目の店が達成すべき大気の綺麗さを表す。

すべての店が大気の綺麗さを達成するために必要な 大気を循環させる回数の最小値を1行に出力せよ。

どのように操作しても達成できない場合には$-1$を出力せよ。

入力中の各変数は以下の制約を満たす。

• $ 3 \leq n \leq 10^{5} $

• $ -10^{8} \leq p_{i} \leq 10^{8} $

• $ 1 \leq l_{i} \leq 10^{8} $