시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 256 MB 205 27 13 68.421%

문제

이번 학기 지스트에는 총 $m$개의 과목이 개설되며, 청응이는 이번 학기에 $n_\text{lo}$학점 이상, $n_\text{hi}$학점 이하를 듣고자 한다. 청응이는 개설 교과목 목록을 보며 모든 강의에 대해 행복도를 매겼고, 이번 학기의 행복도는 수강하는 모든 과목의 행복도의 합으로 정의한다. 시간표는 고려할 필요가 없다. 청응이가 이번 학기 가질 수 있는 최대 행복도를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 최소와 최대 수강 학점 $n_\text{lo}$, $n_\text{hi}$이 공백으로 구분되어 주어진다. 학점은 $0\leq n_\text{lo}\leq n_\text{hi}\leq 200,000$을 만족한다. 둘째 줄에는 이번학기 개설 교과목의 수 $m$이 주어진다. $1\leq m\leq 200,000$을 만족한다. 셋째 줄부터 $(m+2)$번째 줄까지 각 줄마다 개설 과목에 대한 정보가 다음과 같이 주어진다. $(i+2)$번째 줄에 과목 $i$의 학점 $g_i$와 행복도 $s_i$가 공백으로 구분되어 주어지며, 학점은 $0\leq g_i\leq 5$, 행복도는 $-100\leq s_i\leq 100$를 만족한다. 학점 요건을 충족하는 과목들의 조합이 존재하는 경우만 주어진다.

출력

이번 학기 얻을 수 있는 최대 행복도를 출력한다.

서브태스크 1 (20점)

모든 과목의 학점이 $0$학점 혹은 $1$학점인 경우만 주어진다. 즉, 모든 $i$에 대해 $g_i=0$ 혹은 $g_i=1$이다.

서브태스크 2 (30점)

최소와 최대 수강 학점 $n_\text{lo}$, $n_\text{hi}$이 $0\leq n_\text{lo}\leq n_\text{hi}\leq 2,000$을 만족하는 경우만 주어진다.

서브태스크 3 (50점)

추가 제한 조건이 없다.

예제 입력 1

2 2
4
0 2
1 1
1 3
1 -1

예제 출력 1

6

예제 입력 2

3 5
8
0 2
1 2
2 -2
0 -8
1 0
3 -5
1 -3
0 -1

예제 출력 2

2

채점

  • 예제는 채점하지 않는다.