Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Mali Ðurica je našao N kamenčića. Na svakom kamenčiću je napisano jedno velikoslovo engleske abecede (slova od 'A' do 'Z'). On je izmerio svaki kamenčić i utvrdio njegovumasu u gramima. Nakon toga je napisao reč dužine M koja se sastoji samo od velikih slovaengleske abecede. Malog Ðuricu zanima koja je najmanja masa kamenčića, koje treba daizabere, tako da kad ih nekako složi u jedan red dobije prethodno napisanu reč.
Pošto mali Ðurica želi da se igra, ovaj problem je prepustio Vama.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke senalaze celi brojevi N (1 ≤ N ≤ 50000) i M (1 ≤ M ≤ 50000). U narednih N redova se nalazepo jedno slovo si i jedan ceo broj ti, gde sipredstavlja slovo na i-tom kamenčiću (si će uvekbiti veliko slovo engleske abecede), a ti (1 ≤ ti ≤ 50000) masu i-tog kamenčića. Potom se učitava M redova koji sadrže po jedno slovo i to su redom slova reči koju je napisao maliĐurica.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz)U prvom redu datoteke ispisatinajmanju ukupnu masu kamenčića koje je potrebno koristiti da bi se njihovim slaganjemdobila napisana reč. Ako je nemoguće dobiti napisanu reč ispisati -1.

Ogranicenja:

  • 1 ≤ N ≤ 50000
  • 1 ≤ M ≤ 50000
  • 1 ≤ ti ≤ 50000
  • 'A'si'Z'
  • vremensko ogranicenje za izvršavanje programa je 1 s.

Primer 1:

standardni ulaz      standardni izlaz
5 3
A 10
B 40
C 30
B 20
E 50
C
E
B
        
100

Primer 2:

standardni ulaz      standardni izlaz
14 11
A 1
I 2
K 3
L 4
O 5
P 6
N 7
F 8
R 9
O 10
M 11
T 12
I 13
Z 14
I
N
F
O
R
M
A
T
I
K
A
        
-1

Comments

There are no comments at the moment.