수도배관공사

아기 염소들은 언덕에서 풀을 뜯고 놀다가 자주 목이 말랐다. 그래서 거리 D만큼 떨어진 강에서 물을 끌어오기 위해 수도관 하나를 만들려고 한다.

염소들은 근처 마을에서 파이프 P개를 구했다. i번째 파이프는 길이 L_i와 용량 C_i를 가진다. D는 7 이상 100,000 이하이고, P는 1 이상 350 이하이다. L_i와 C_i는 모두 2^23 이하의 양의 정수이다.

파이프는 각각 최대 한 번 사용할 수 있으며, 선택한 파이프들을 일렬로 이어 수도관 하나를 만든다. 이때 수도관의 길이는 선택한 파이프 길이의 합이고, 수도관의 용량은 선택한 파이프 용량 중 최솟값이다.

총 길이가 정확히 D인 수도관을 만들 때, 가능한 수도관 용량의 최댓값을 구하라.

첫째 줄에 D와 P가 주어진다.

다음 P개의 줄에는 각 파이프의 길이 L_i와 용량 C_i가 한 줄에 하나씩 주어진다.

길이의 합이 D가 되는 파이프 부분집합이 적어도 하나 존재한다.

총 길이가 정확히 D인 수도관을 만들 때 가능한 최대 용량을 첫째 줄에 출력한다.