Kingikott

시간 제한1초메모리 제한1024 MB

요약

상점에 있는 두 상품의 가격을 최대 한 번 맞바꾼 뒤, 목록에 있는 M개의 선물을 사는 최소 비용을 구한다.

난이도: 보통10점 중 4점
유형: 배열, 그리디, 정렬, 해시맵
정답자: 아직 제출이 없습니다

문제

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 $N$ ( $1 \le N \le 1\\,000$ ).

Järgmisel $2 \cdot N$ real on $N$ 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 $P$ ( $1 \le P \le 1\\,000$ ). Võib eeldada, et kaupade nimetused poes on unikaalsed.

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

Järgmisel $M$ 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.

예제2

예제 1

입력

3
mudelauto
10
legokomplekt
20
raamat
30
4
mudelauto
raamat
legokomplekt
raamat

예상 출력

예제 2

입력

3
mudelauto
10
legokomplekt
20
raamat
30
2
mudelauto
mudelauto

예상 출력