Problem 3377: F

Cerință

Vrei să formezi un cuvânt și nu ai destule litere din cele care îți trebuie, și ai altele nefolositoare. Din fericire vrăjitorul Jaxson are $M$ oferte pentru tine: "Dă-mi litera $L_1$ și $X$ galbeni și îți voi da litera $L_2$ ". Vei face tot posibilul să îți construiești cuvântul. Poți să îl formezi? Dacă da, care este numărul minim de galbeni care trebuie plătiți?

Să se rezolve $T$ teste.

Date de intrare

Pe prima linie se află $T$ , urmând $T$ teste.
Pentru fiecare test se citesc în ordine: cuvântul pe care vrei să il formezi, stocul tău de litere, numărul de oferte și ofertele (Explicația este în exemplu).
Stocul tău de litere este un șir de $26$ de numere naturale. Primul număr este câte litere $a$ ai în stoc, al doilea câte litere $b$ ...

Date de ieșire

Se afișează $T$ rânduri, pe fiecare rând este fie $"NU"$ , fie $"DA"$ urmat de costul minim care trebuie plătit.

Restricții și precizări

$1 \leq T \leq 5$
Se garantează că perechile de litere citite sunt distincte.
Lungimea cuvântului citit în fiecare test este $\leq 10^6$ .
Numărul de copii dintr-o literă inițial este $\leq 10^6$ .
Costul pentru un schimb este strict pozitiv și $\leq 10^9$

Exemplul 1

stdin

5
aab
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
a b 1
aab
0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
c d 1
d a 1
c b 1
abc
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
a b 1
abbcb
2 2 2 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
a b 5
c b 4
abcd
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 1999
4
a b 6
d c 1
c b 2
a d 1

stdout

DA 1
DA 5
NU
DA 4
DA 7

Explicație

Pentru primul test avem la dispoziție literele ${'a', 'a', 'a'}$ și vrem să formăm cuvântul $aab$ , pentru asta ne vom folosi de singura ofertă și vom da la schimb o literă $a$ pentru una $b$ la costul de $1$ , acuma avem literele ${'a','a','b'}$ , cu acestea putem forma cuvintele $aab$ , $aba$ , $baa$ .

Pentru testul doi vom schimba un $c$ în $b$ după care $2$ de $c$ pentru $2$ de $d$ , după care $2$ de $d$ pentru doi de $a$ .

Pentru testul $3$ nu avem cum să ne formăm cuvântul doar din ofertele disponibile.

Pentru testul patru, putem fie să schimbăm un $a$ în $b$ , fie un $c$ în $b$ , vom schimba $c$ -ul deoarece are un cost mai mic schimbul acela. Se obervă că avem și $8$ litere $f$ , dar aceasta nu ne ajută sau încurcă cu nimic.

F - Jamne