CSES - Ritarit
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Pyöreän pöydän ritarit ovat asettuneet syömään, mutta jokin on pahasti pielessä!

Jokainen ritari on toimittanut etukäteen tiedon, montako kiloa ruokaa tarvitsee. Mutta tarjoilijat ovat olleet huolimattomia eivätkä ruokamäärät täsmää. Vain ruoan kokonaismäärä on oikea.

Joka vuorolla yksi ritari voi siirtää kilon ruokaa hänen vieressään istuvalle ritarille. Mikä on pienin määrä vuoroja, joiden jälkeen jokaisella ritarilla on oikea määrä ruokaa?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ritarien määrä.

Sitten syötteessä on n kokonaislukua a_1,a_2,\ldots,a_n: montako kiloa ruokaa kukin ritari tarvitsee.

Lopuksi syötteessä on n kokonaislukua b_1,b_2,\ldots,b_n: montako kiloa ruokaa kukin ritari on saanut eteensä.

Tuloste

Tulosta yksi kokonaisluku: pienin vuorojen määrä.

Rajat

  • 1 \le n \le 2 \cdot 10^5
  • 0 \le a_i \le 10^9
  • 0 \le b_i \le 10^9

Esimerkki

Syöte:

5
1 1 1 1 1
2 3 0 0 0

Tuloste:

4

Selitys: Jokainen ritari tarvitsee kilon ruokaa. Aluksi ritari 1:n edessä on kaksi kiloa ruokaa ja ritari 2:n edessä on kolme kiloa ruokaa. Ratkaisu: Ritari 1 siirtää ensin kilon ruokaa ritari 5:lle. Sitten ritari 2 siirtää kahdesti kilon ruokaa ritari 3:lle. Lopuksi ritari 3 siirtää kilon ruokaa ritari 4:lle.