Annettuna on kaksi bittijonoa, joissa molemmissa on n bittiä. Tehtäväsi on muuttaa ensimmäinen bittijono toiseksi kahden operaation avulla:

• Operaatio 1: Muuta mikä tahansa yksi bitti käänteiseksi (kustannus a)
• Operaatio 2: Muuta kaikki bitit tietyltä väliltä käänteisiksi (kustannus b)

Saat suorittaa kummankin operaation haluamasi määrän kertoja. Mikä on pienin mahdollinen kokonaiskustannus?

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua n, a ja b: bittijonon pituus sekä operaatioiden kustannukset.

Tämän jälkeen tulee kaksi riviä, jotka sisältävät bittijonot.

Tuloste

Tulosta yksi kokonaisluku: pienin kokonaiskustannus.

Esimerkki

Syöte:

8 3 5
10110001
01101000

Tuloste:

11

Selitys: Suoritetaan ensin operaatio 2 välille 1 \dots 5, jolloin bittijonosta 10110001 tulee 01001001. Tämän jälkeen suoritetaan operaatio 1 kohtiin 3 ja 8, jolloin tuloksena on lopullinen bittijono 01101000. Operaatioiden kustannus on 5+3+3=11.

Osatehtävä 1 (21 pistettä)

• 1 \le n \le 10
• 1 \le a, b \le 1000

Osatehtävä 2 (16 pistettä)

• 1 \le n \le 10^5
• 1 \le a, b \le 10^9
• a \ge b

Osatehtävä 3 (63 pistettä)

• 1 \le n \le 10^5
• 1 \le a, b \le 10^9