BnPC

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

요약

속성마다 가진 k개의 능력치 포인트를 분배해 모든 이벤트의 임계값을 통과하면서, 임계값을 초과한 이벤트에서 얻는 점수의 합이 최대가 되도록 만든다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

좋아하는 게임 Basements and Pigeonlike Creatures를 몇 번째인지 모를 만큼 다시 하고 있다. 게임에 꽤 익숙하지만, 최선의 전략을 찾을 만큼 충분히 시간을 들인 적은 없었다. 지금부터는 다르다. 게임은 몬스터와 싸우거나 나무에 오른 고양이를 구하는 등의 사건이 일정한 순서로 이어지며, 모든 사건을 완수해야 승리한다. 각 사건에는 힘 같은 능력치와 양의 정수인 기준값이 붙어 있다. 능력치 점수가 기준값 이상이면 그 사건을 성공적으로 완수한다. 그렇지 않으면 아쉽게도 게임 오버이고, 총점은 0이 된다.

모든 사건을 성공적으로 완수하면 점수는 각 사건에서 얼마나 잘했는지에 따라 달라진다. 능력치 점수가 사건의 기준값과 정확히 같으면 그 사건을 간신히 넘긴 것이므로 0점을 얻는다. 기준값을 초과하면 그 사건에 사용한 능력치 점수만큼 점수를 얻는다.

이제 게임의 마지막 부분에 왔지만, 먼저 능력치 점수를 얼마간 써서 능력치를 올려야 한다. 마지막 부분에서 어떤 사건이 일어날지 알고 있으니, 남은 일은 어떤 능력치를 올릴지 정하는 것뿐이다.

입력

입력은 다음과 같다.

정수 $n$ ( $1 \leq n \leq 10^5$ )과 정수 $k$ ( $1 \leq k \leq 10^9$ )가 있는 한 줄. $n$ 은 능력치의 수, $k$ 는 아직 쓸 수 있는 능력치 점수의 수다.
$n$ 개의 줄. 각 줄에는 서로 다른 능력치 이름과 그 능력치의 현재 점수인 정수 $s$ ( $0 \leq s \leq 10^9$ )가 있다.
정수 $l$ ( $1 \leq l \leq 10^5$ )이 있는 한 줄. $l$ 은 사건의 수다.
$l$ 개의 줄. 각 줄은 사건 하나를 나타내며, 사용하는 능력치의 이름과 그 사건의 기준값인 정수 $t$ ( $0 \leq t \leq 10^9$ )가 있다.

능력치 이름은 영문 대문자(A-Z)로 이루어지며 길이는 $1$ 이상 $20$ 이하다.

출력

사건에서 얻을 수 있는 최대 점수를 출력한다.

예제2

예제 1
입력
```
2 3
STR 15
CON 12
2
STR 17
CON 14
```
예상 출력
```
0
```

예제 2

입력

3 7
JUMP 5
RUN 7
FLY 0
4
FLY 0
JUMP 6
RUN 10
RUN 8

예상 출력