Team Running Selection

It is sports day. The students want to choose a team for a group running event. Every team member starts at the same time and runs from the starting line to the finish line.

A team's result is determined by the arrival time of its last member. Therefore, the team should be chosen so that the slowest selected student's running speed is as large as possible.

There is one additional condition: the sum of the selected team members' heights must be exactly H. As long as the height sum is H, the number of selected students does not matter.

Given each student's height and running speed, write a program that maximizes the running speed of the slowest member of a valid team.

The first line contains the target height sum H and the number of students N.

Each of the next N lines contains two integers, h_i and s_i, where h_i is the height of the i-th student and s_i is that student's running speed.

Print the maximum possible running speed of the slowest member among all valid teams.

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