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