점수 인플레이션
면접 대비시간 제한1초메모리 제한1024 MB
대회 시간 M분과 N개 문제 종류의 배점과 풀이 시간이 주어질 때, 각 종류의 문제를 제한 없이 골라 M분 안에 얻을 수 있는 최대 점수를 구합니다.
문제
USACO 대회에서 학생들이 더 많은 점수를 얻을수록 운영진은 기쁩니다. 운영진은 참가자가 최대한 많은 점수를 얻을 수 있도록 대회를 설계하려고 하며, 이를 도와주세요.
카테고리는 문제들의 무한 집합입니다. 같은 카테고리의 문제는 모두 풀이 시간이 같고, 정답을 맞히면 같은 점수를 줍니다. 각 카테고리에서 몇 문제를 대회에 넣어야 총점이 최대가 되는지 알려주는 프로그램을 작성하세요. 단, 총 풀이 시간은 대회 시간을 넘으면 안 됩니다. 각 카테고리에서 고르는 문제 수는 0 이상의 정수이면 됩니다(0개, 1개, 여러 개 모두 가능). 얻을 수 있는 최대 점수를 구하세요. (걱정하지 마세요. 훈련 캠프 전까지는 더 긴 대회에 나갈 일이 없습니다.)
입력
첫 줄에 대회 시간 M(분)과 문제 카테고리 수 N이 주어집니다. 1 ≤ M ≤ 10,000, 1 ≤ N ≤ 10,000입니다.
이어지는 N개의 줄에는 각 카테고리를 나타내는 두 정수가 주어집니다. 첫 번째 정수는 그 카테고리 문제 하나의 점수(1 ≤ 점수 ≤ 10000)이고, 두 번째 정수는 그 문제를 푸는 데 걸리는 시간(분)(1 ≤ 시간 ≤ 10000)입니다.
출력
제약 조건을 지키면서 얻을 수 있는 최대 점수를 한 줄에 출력하세요.