Državno natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) – drugi dan natjecanja - 3. zadatak

Zadan je string sastavljen od nula i jedinica – takozvani traženi string. Zadano je i dodatnih n stringova koje zovemo pomoćnim stringovima.

Traženi string potrebno je složiti nadovezivanjem (povezivanjem s lijeva na desno) manjih dijelova od kojih svaki mora biti prefiks ili sufiks nekog pomoćnog stringa.

Svaki pomoćni string možemo koristiti proizvoljan broj puta za prefikse i/ili sufikse, ali za svako njegovo korištenje valja platiti cijenu od ci kuna (pri čemu je i redni broj pomoćnog stringa).

Napišite program koji računa minimalnu ukupnu cijenu potrebnu da traženi string složimo od prefiksa i/ili sufiksa zadanih pomoćnih stringova.

Ulazni podaci

U prvom je retku prirodan broj n (1 ≤ n ≤ 200 000), broj pomoćnih stringova.

U drugom je retku traženi string sastavljen od m (1 ≤ m ≤ 200 000) nula i jedinica.

Svaki od idućih n redaka sadrži prirodan broj ci (1 ≤ ci ≤ 109) i potom neprazan pomoćni string sastavljen od nula i jedinica, pri čemu je ci cijena njegovog korištenja.

Za ukupnu duljinu L svih pomoćnih stringova vrijedi L ≤ 200 000.

Izlazni podaci

U jedini redak ispišite traženu minimalnu ukupnu cijenu ili broj −1 ako traženi string nije moguće složiti.

Primjer zadatka

Ulaz

2
111001011
1 011
1 00110

Izlaz

4

Objašnjenje

Pojašnjenje prvog probnog primjera: 111001011 = 11 + 1 + 001 + 011. Prvi, drugi i četvrti dio uzimamo kao sufikse pomoćnog stringa 011, a treći dio kao prefiks pomoćnog stringa 00110.

Ulaz

3
101001010
3 1010
10 100
2 011

Izlaz

8

Objašnjenje

Pojašnjenje drugog probnog primjera: 101001010 = 1010 + 0 + 1010. Prvi i treći dio uzimamo od

pomoćnog stringa 1010 (za što dvaput plaćamo cijenu 3), a drugi od pomoćnog stringa 011 (cijena 2).