16138번 - 수강신청 서브태스크

문제

이번 학기 지스트에는 총 $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점)

추가 제한 조건이 없다.

힌트