Mastot

• Time limit: 1.00 s
• Memory limit: 512 MB

Haluat muodostaa radioyhteyden etäisyyden $n$ päässä olevaan vastaanottimeen. Radiolähettimesi kantama ei kuitenkaan välttämättä riitä, ja voit joutua välittämään signaalin mastojen kautta.

Lähettimen ja vastaanottimen välissä on tasavälein $n-1$ mastoa etäisyyksillä $1, 2, \dots, n-1$ lähettimestä. Mastot lähettävät edelleen vastaanottamansa signaalit. Lähettimellä ja kullakin mastolla on kantama $d_i$, joka kuvaa molempiin suuntiin suurinta etäisyyttä, jolla kyseisestä paikasta lähetetyn signaalin voi vastaanottaa.

Kaikki mastot ovat kuitenkin epäkunnossa, ja maston $i$ korjaamisen hinta on $c_i$.

Mikä on pienin kokonaishinta, jolla saat vastaanottimeen yhteyden?

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku $n$: vastaanottimen etäisyys.

Toisella rivillä on $n$ kokonaislukua $d_0, d_1, ..., d_{n-1}$: lähettimen kantama ja mastojen kantamat.

Kolmannella rivillä on $n-1$ kokonaislukua $c_1, ..., c_{n-1}$: mastojen korjauksien hinnat.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kokonaishinta.

Esimerkki

Syöte:
6
2 2 3 1 2 4
4 1 3 4 2

Tuloste:
3

Selitys: Optimaalinen ratkaisu on korjata mastot etäisyyksillä $2$ ja $5$.

Kaikissa osatehtävissä pätee $1 \leq d_i \leq n$ ja $1 \leq c_i \leq 10^9$.

Osatehtävä 1 (11 pistettä)

• $2 \leq n \leq 20$
  

Osatehtävä 2 (34 pistettä)

• $2 \leq n \leq 5000$
  

Osatehtävä 3 (55 pistettä)

• $2 \leq n \leq 2 \cdot 10^5$