팀 달리기 선발

오늘은 즐거운 체육 대회 날이다. 학생들은 단체 달리기에 출전할 팀을 고르려고 한다. 모든 팀원은 출발선에서 결승선을 향해 동시에 출발한다.

팀의 기록은 팀원 중 가장 늦게 도착한 사람의 도착 시간으로 결정된다. 따라서 팀을 고를 때에는 선택한 팀원 중 가장 느린 학생의 달리기 속도가 최대가 되도록 해야 한다.

이번 대회에는 한 가지 추가 조건이 있다. 출전 팀원들의 키를 모두 더한 값이 정확히 H가 되어야 한다. 키의 합이 H이기만 하면 팀원 수에는 제한이 없다.

학생들의 키와 달리기 속도가 주어질 때, 조건을 만족하는 팀에서 가장 느린 팀원의 달리기 속도를 최대화하는 프로그램을 작성하시오.

첫 줄에 목표 키 합 H와 학생 수 N이 주어진다.

다음 N개의 줄에는 각 학생의 키 h_i와 달리기 속도 s_i가 주어진다. h_i와 s_i는 각각 i번째 학생의 키와 속도이다.

조건을 만족하는 팀을 만들었을 때, 가장 느린 팀원의 달리기 속도로 가능한 최댓값을 출력한다.

• 7 <= H <= 100,000
• 1 <= N <= 350
• 1 <= h_i, s_i <= 100,000