저지

면접 대비

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

요약

각 선수가 요청한 번호의 유니폼을 최소 희망 사이즈 이상으로 줄 때 만족할 수 있는 최대 인원을 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

학교 대표팀이 1번부터 J번까지 번호가 붙은 저지를 선수에게 나눠 주려고 한다. 저지의 사이즈는 S, M, L 중 하나다.

선수는 각자 받고 싶은 저지 번호 하나와 선호하는 사이즈를 말했다. 요구한 번호가 아닌 저지를 받거나 선호하는 사이즈보다 작은 저지를 받으면 그 선수는 불만을 품는다. 선수를 만족시키려면 저지 번호가 요구한 번호와 같고, 사이즈가 선호하는 사이즈와 같거나 더 커야 한다. 사이즈는 S, M, L 순서로 커진다. 저지 하나를 두 선수가 나눠 받을 수는 없다.

만족시킬 수 있는 선수의 최대 인원을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 저지의 수 J가 주어진다.

둘째 줄에 선수의 수 A가 주어진다.

이어지는 J줄에는 번호가 j인 저지의 사이즈가 한 줄에 하나씩 주어진다 ( $1 \le j \le J$ ).

마지막 A줄에는 선수가 요구하는 사이즈와 저지 번호가 공백 하나를 사이에 두고 주어진다. 저지 번호는 1 이상 J 이하다.

테스트 케이스의 50%는 $1 \le J \le 10^3$ , $1 \le A \le 10^3$ 을 만족하고, 나머지 50%는 $1 \le J \le 10^6$ , $1 \le A \le 10^6$ 을 만족한다.

출력

만족시킬 수 있는 선수의 최대 인원을 출력한다.

힌트

예제에서 1번 저지는 M인데 1번을 요구한 선수는 L을 선호하므로 이 저지는 아무에게도 줄 수 없다. 2번 저지와 4번 저지는 아무도 요구하지 않았다. 3번 저지는 3번을 요구하면서 S를 선호한 선수에게 준다.

예제7

예제 1
입력
```
4
3
M
S
S
L
L 3
S 3
L 1
```
예상 출력
```
1
```
예제 2
입력
```
1
1
S
S 1
```
예상 출력
```
1
```
예제 3
입력
```
1
1
S
L 1
```
예상 출력
```
0
```
예제 4
입력
```
3
3
L
L
L
S 1
M 2
L 3
```
예상 출력
```
3
```
예제 5
입력
```
2
4
M
M
S 1
M 1
S 1
L 2
```
예상 출력
```
1
```
예제 6
입력
```
3
3
S
S
S
M 1
L 2
M 3
```
예상 출력
```
0
```
예제 7
입력
```
6
5
M
L
S
M
L
S
M 1
S 3
L 5
M 6
L 2
```
예상 출력
```
4
```