Trail Running Team Speed

You are participating in a team competition of trail running. There are \( n \) members in your team. The \( i \)-th member has a speed \( v_i \) and a weight \( w_i \).

Each team member can either run alone or carry one other member on their back. When member \( i \) carries member \( j \), the following rules apply:

• If \( w_i \ge w_j \), then member \( i \)'s speed remains \( v_i \).
• If \( w_i < w_j \), then member \( i \)'s speed decreases by \( (w_j - w_i) \) and becomes \( v_i - (w_j - w_i) \). If this value becomes negative, then member \( i \) cannot carry member \( j \).

Each member can carry at most one other member. Also, a member being carried cannot carry anyone. For all members who are not being carried (i.e. the runners), the team’s speed is defined as the minimum speed among them (after applying any speed reduction due to carrying). Your task is to determine the maximum possible team speed that can be achieved by optimally deciding who runs and who is carried.

Note: The answer is the maximum value \( S \) such that it is possible to assign each member to either run or be carried, and for every runner, their adjusted speed is at least \( S \).

inputFormat

The first line contains an integer \( n \) indicating the number of team members.

Each of the following \( n \) lines contains two integers \( v_i \) and \( w_i \), representing the speed and weight of the \( i \)-th member respectively.

\( 1 \le n \le 10^5 \) (constraints may be set accordingly) and \( v_i, w_i \) are positive integers.

outputFormat

Output a single integer, the maximum possible speed of the team.

sample

3
5 4
3 3
4 2

4