cho.sh

Air Pollution

아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

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

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

  • p′_i−1=p_i−1+p_ip'\_{i-1} = p\_{i-1} + p\_{i}

  • p′_i=p_i−2p_ip'\_{i} = p\_{i} - 2 p\_{i}

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

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

입력

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

nn

p_1p\_{1} ... p_np\_{n}

l_1l\_{1} ... l_nl\_{n}

nnは店の数、p_ip\_{i}はii番目の店の現在の大気の綺麗さ、l_il\_{i}はii番目の店が達成すべき大気の綺麗さを表す。

출력

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

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

제한

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

  • 3≤n≤1053 \leq n \leq 10^{5}

  • −108≤p_i≤108-10^{8} \leq p\_{i} \leq 10^{8}

  • 1≤l_i≤1081 \leq l\_{i} \leq 10^{8}