- Time limit: 1.00 s
- Memory limit: 512 MB
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$
- $2 \leq n \leq 5000$
- $2 \leq n \leq 2 \cdot 10^5$