시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB300977636.364%

문제

오늘은 즐거운 체육 대회이다. 학생들은 그룹 달리기에 출전할 팀을 선발하려고 한다. 그룹달리기는 말아톤과 같은 형식이다. 모든 팀의 구성원들이 출발지점에서 골인지점을 향해 동시에 출발을 한다. 팀의 성적은 그 팀의 구성원 중 가장 늦게 도착한 사람의 도착시간으로 하기 때문에 구성원 중 달리기 속도가 가장 느린 사람이 가장 빠르게 되도록 팀을 선발해야 한다. 이번 대회에서는 팀을 선발할 때 특별한 제약조건이 하나 있는데 그것은 출전 팀 구성원들의 키를 모두 더했을 때 정확히 H가 되어야 한다는 것이다. 키의 합이 H만 된다면 구성원이 몇 명이 되든 상관이 없다.

학생 중에서 그룹달리기에 출전할 팀을 선발하는 프로그램을 작성하시오.

입력

첫 번째 줄엔 H와 학생 수인 N이 주어진다.

두 번째 줄부터 학생들의 정보 hi, si가 주어지는데 hi는 i번째 학생의 키이며 si는 i번째 학생의 달리기 속도이다.

출력

출전 팀 구성원 중 가장 느린 사람의 달리기 속도를 출력하시오.

제한

  • 7 ≤ H ≤ 100,000
  • 1 ≤ N ≤ 350
  • 1 ≤ hi, si ≤ 100,000

예제 입력 1

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

예제 출력 1

5