문제
준혁이는 그림 전시회를 열려고 한다.
전시회에서, 준혁이는 몇 개의 그림을 액자에 넣고 일렬로 전시하려고 한다.
전시할 그림 후보로는 1번부터 N번까지의 번호가 붙어 있는 N개의 그림이 있다.
i번 그림(1 ≤ i ≤ N)의 크기는 Si이며, 가치는 Vi이다.
액자 또한, 1번부터 M번까지의 번호가 붙어 있는 M개의 액자가 있다.
j번 액자(1 ≤ j ≤ M)의 크기는 Cj이다.
Cj 이하의 크기를 가진 그림만 j번 액자에 들어갈 수 있으며, 한 개의 액자에는 최대 한 개의 그림만 들어갈 수 있다.
전시할 모든 그림은 액자에 들어가서 전시되어야 한다.
미관상의 아름다움을 위해, 그림들은 다음의 조건을 충족시켜야 한다;
- 액자의 크기는 단조증가하여야 한다.
- 그림의 가치는 단조증가하여야 한다.
준혁이는 최대한 많은 그림을 전시하고 싶다.
당신은 준혁이를 도와, 전시할 수 있는 그림의 수의 최댓값을 구해주자.
액자와 그림의 순서는 초기순서를 유지할 필요가 없다.
입력
첫 번째 줄에는 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100,000)
이어지는 N개의 줄 중 i번째 줄에는 Si와 Vi가 공백으로 구분되어 주어진다.
(1≤ Si, Vi ≤ 1,000,000,000)
이어지는 M개의 줄 중 j번째 줄에는 Cj가 주어진다. (1 ≤ Cj ≤ 1,000,000,000)
출력
전시할 수 있는 그림의 수의 최댓값을 구하여 출력한다.
예제
3 4
10 20
5 1
3 5
4
6
10
4
2
출처
20201031 집중강화학습3차3번,dennisstar,JOI 2019 2번
로그인해야 코드를 작성할 수 있어요.