시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 185 41 31 24.800%

문제

아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7<=D<=100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1<=P<=350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 24비트 양의 정수이다)

파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이 때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최소값이 되고, 수도관의 길이는 파이프들 길이의 총합이다.

수도관을 한 개 만들어 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 D와 P가 주어진다.
  두번째 줄부터 P개의 줄이 차례로 주어지고, 각 줄마다 Li와 Ci가 주어진다.

출력

가능한 최대 수도관 용량을 첫째 줄에 출력한다.

예제 입력

7 6
4 5
3 6
2 7
1 4
6 7
1 5

예제 출력

5

힌트