Farse

Miki și Andrei s-au reunit, cu ajutorul vostru, fix înainte de ziua de Halloween și vor să se distreze împreună în spiritul acestei sărbători. Andrei a găsit în castelul său o carte cu numere de telefon și acum îi propune lui Miki să facă farse la telefon și să sperie oamenii ce le răspund.
Lui Miki îi place ideea, dar propune să facă acest lucru într-un mod cât mai puțin costisitor.

Pe prima pagină a cărții se află informațiile celor $N$ centrale telefonice disponibile, adică prefixul pe care îl deservesc (un șir de cifre $P_i$) și costul pentru a suna la centrala respectivă (un număr natural $C_i$). O centrală poate fi folosită pentru a apela orice număr de telefon care începe cu prefixul acelei centrale.

După primele câteva încercări, Miki și Andrei descoperă un secret, anume că centralistele cu prefixe similare sunt prietene între ele și sunt dispuse să le facă legătura la o altă centrală, dar pentru un cost, evident. Prin urmare, dacă cei doi vor de la o anumită centrală $i$ să fie conectați la altă centrală $j$, aceștia trebuie să plătească $X \times d(P_i, P_j)$ unde $d(P_i, P_j) =$ plecând de la prefixul $P_i$, câte cifre trebuie șterse de la final $+$ câte cifre trebuie apoi adăugate la final pentru a obține prefixul $P_j$. În alte cuvinte, de câte operații este nevoie într-un editor text care permite doar scriere la final și tasta backspace pentru a îl transforma pe $P_i$ în $P_j$ (pentru că asta este ce are de făcut centralista ca să redirecționeze apelul).

Cerință

Se dau prefixele și costul pentru fiecare operație. Miki și Andrei aleg aleator din carte $Q$ numere de telefon și vă roagă să le aflați costul minim de a face farse acestor numere.

Date de intrare

Pe prima linie a intrării se află $N$, $Q$ și $X$. Pe fiecare dintre următoarele $N$ linii se găsesc un șir de cifre $P_i$ și un întreg pozitiv $C_i$, separate printr-un spațiu, reprezentând prefixul și costul celei de-a $i$-a centrale.

Pe următoarele $Q$ linii se află câte un număr de telefon reprezentat de un șir de cifre.

Date de ieșire

Afișați $Q$ linii, fiecare conținând câte un număr întreg, al $i$-lea dintre acestea reprezentând costul minim de apelare al $i$-lealui număr de telefon din intrare, dacă numărul respectiv poate fi apelat, sau $-1$ în caz contrar.

Restricții și precizări

• $1 \leq N, Q \leq 1\ 000\ 000$
• $1 \leq S_p \leq 1\ 000\ 000$, unde $S_p =$ suma lungimilor prefixelor
• $1 \leq S_t \leq 1\ 000\ 000$, unde $S_t =$ suma lungimilor numerelor de telefon
• $0 \leq C_i \leq 10^9$ pentru $1 \leq i \leq N$
• $0 \leq X \leq 10^9$
• Nu există niciun prefix mai lung decât un număr de telefon

Exemplu

stdin

5 4 2
0722 5
0213 2
02 7
902 10
07 2
072212352423
021435246
9022432342
90358293022

stdout

2
6
10
-1

Explicație

Pentru numărul de telefon $072212352423$ folosim prefixul $07$ de cost $2$.

Pentru numărul de telefon $021435246$ plecăm de la prefixul $07$ pe care îl modificăm astfel:

• Ștergem $7$
• Adăugăm $2$ la final

și ajungem la prefixul $02$. Cele două operații costă în total $2 \times X = 4$ și adunat cu costul prefixului avem un cost total de $6$.

Pentru numărul de telefon $9022432342$ folosim prefixul $902$ de cost $10$.

Pentru numărul de telefon $90358293022$ nu avem niciun prefix care să se potrivească.

Note asupra ediției

În caz că vă plictisiți încercând să rezolvați această problemă, am decis să vă includem și câteva exemple de farse jucate de Miki și Andrei. Nu sunt neapărat bune, dar sperăm că vă veți bucura de ele:

• "Alo, vă merge frigiderul? ...Atunci fugiți după el să nu ajungă prea departe"
• "Alo, avem nevoie de ajutor. Goblinul Ragnok s-a îndrăgostit de paladina noastră, dar nu are suficiente aura points pentru a o cuceri. Îi puteți dona câteva?"
• "Buna ziua, un porc mistreț înflăcărat a fost văzut dând târcoale prin zona dvs. Baricadați bine ușile și ferestrele și păziți-vă fiicele."
• "Nu ați aflat încă de cea mai nouă modă glamour leopard? Este foarte simplu, vă puteți programa chiar acum pentru un transplant de blană autentică!"
• "Bună ziua, strângem daruri pentru nunta lui Dracula... Vă rugăm nu dați țepe!"
• "[într-un growl agresiv] Don't lock the door on me...[apoi continuând pe un ton foarte politicos] pentru a continua programul nesolicitat de death metal, apăsați tasta 1"
• "Bună ziua, vă contactăm pentru un sondaj de opinie în legătură cu produsele de panificație pe care le-ați primit recent. Le găsiți prea ațoase ați zis? Păi normal, doar sunt făcute din croșet!!!"