문제
N명의 어린이를 수용하고 있는 보육원에 크리스마스 이브날 밤 산타할아버지가 굴뚝으로 들어와서 여러 종류의 막대사탕을 양말에 넣고 가셨다. 막대사탕의 포장에는 각각의 당도가 표시되어 있었다. 보육원 아이들은 당도가 너무 낮은 것을 싫어하는 아이도 있고 이가 썩어서 당도가 높은 것을 먹으면 안되는 아이도 있다.
원장님은 한 아이에게 최대 한 개씩 가능한 많은 아이들에게 사탕을 나누어주려고 한다. 아이들마다 먹을 수 있는 당도의 범위가 주어진다면 막대사탕을 나누어 줄 수 있는 아이는 최대 몇 명인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 어린이의 수 N과 막대사탕의 종류 M이 주어진다. ( 1 ≤ N, M ≤ 2,000 ) 두 번째 줄부터 N개의 줄에 걸쳐 보육원 각각의 아이들이 막대사탕을 먹을 수 있는 당도의 범위가 최소값과 최대값으로 주어진다. ( 1 ≤ 최소값 ≤ 최대값 ≤ 1,000 ) 그 다음 줄부터 M개의 줄에는 각 종류별 막대사탕의 당도와 개수가 주어진다. ( 1 ≤ 당도 ≤ 1,000, 1 ≤ 개수 ≤ 30 ) 입력되는 모든 수는 자연수이다.
<제약조건> 전체 데이터의 30%는 1 ≤ N, M ≤ 20 이다.
출력
막대사탕을 나누어줄 수 있는 최대 어린이의 수를 출력한다.
예제
4 2
3 10
2 5
6 7
1 4
8 2
4 2
3
출처
kyio2013(성결대)
로그인해야 코드를 작성할 수 있어요.