Under construction

Still being built. Things may change

Bsil's Admission Strategy

Interview

Time limit1sMemory limit1024 MB

Summary
Given subject scores, find the minimum and maximum total of M subjects that must include the K publicly announced ones.
Level

Easy3 of 10

Topics
Sorting, Hash map, Greedy
Solved
No attempts yet

Problem

Bsil is a senior in high school this year. Bsil wants to get into Bronze-Silver University (Bsil University), the best university in the world, and plans an admission strategy based on current grades. Bsil University decides whether an applicant passes the document screening by the sum of grades in certain subjects. However, the university does not reveal every subject that counts toward the document review. It publishes only some of them, which makes it a wicked school. Given the number of subjects the university requires and the subjects it publicly says count, find the minimum and maximum scores Bsil can get.

The public subjects and the non-public subjects are all among the subjects Bsil took, and no subject is repeated.

Input

The first line contains the number of subjects NN that Bsil took, the number of subjects MM that Bsil University requires, and the number of subjects KK that the university publicly announced, separated by spaces. (1≤K≤M≤N≤10 000)(1 \le K \le M \le N \le 10\,000)

The next NN lines each contain a subject name sis_i and an integer score pip_i, separated by a space. sis_i consists only of lowercase English letters. (3≤∣si∣≤20;(3 \le |s_i| \le 20; 0≤pi≤100)0 \le p_i \le 100)

The next KK lines each contain a subject name tit_i that the university publicly announced. tit_i consists only of lowercase English letters. (3≤∣ti∣≤20)(3 \le |t_i| \le 20)

Output

Print the minimum and maximum scores Bsil can get, separated by a space.

Examples1

  1. Example 1

    Input
    6 3 2
calculus 100
probability 70
physics 50
chemistry 80
python 90
algorithm 100
physics
python
    Expected output
    210 240