Kingikott

문제

Jõuluvana on koostanud nimekirja kinkidest, mida sellel aastal lastele viia. Iga kingi kohta on teada selle hind poes. Poemüüja, oletades, et jõuluvana pole kõige nupukam, pakub järgmist allahindlust: jõuluvana võib kahe poes müügil oleva kaubaartikli hinnad omavahel ära vahetada. Aita jõuluvanal välja mõelda, millised hinnad tuleks omavahel vahetada, et kingitustele kuluv summa oleks vähim võimalik.

입력

Sisendi esimesel real on poes olevate kaubaartiklite arv $NN$ ($1\le N\le 10001\; \backslash le\; N\; \backslash le\; 1\backslash ,000$).

Järgmisel $2\cdot N2\; \backslash cdot\; N$ real on $NN$ kaherealist plokki. Iga ploki esimesel real on ühe kaubaartikli nimetus (1 kuni 20 väikest ladina tähte) ja teisel real selle täisarvuline hind $PP$ ($1\le P\le 10001\; \backslash le\; P\; \backslash le\; 1\backslash ,000$). Võib eeldada, et kaupade nimetused poes on unikaalsed.

Järgmisel real on jõuluvana nimekirjas olevate kinkide arv $MM$ ($1\le M\le 10001\; \backslash le\; M\; \backslash le\; 1\backslash ,000$).

Järgmisel $MM$ real on igaühel ühe nimekirjas oleva kingi nimetus. Võib eeldada, et neid kõiki on poes piisavas koguses olemas.

출력

Väljastada üks arv: vähim võimalik summa, mille eest saab kõik nimekirjas olevad kingid osta, kui enne arve kokkulöömist võib (aga ei pea) omavahel vahetada kahe artikli hinnad.