Job Assignment

1.0s 256M

There are \(N\) employees in your company, numbered from \(1\) to \(N\).

The company received two orders today, each of which must be completed by a single employee. Employee \(i\) requires time \(A_i\) to complete the first order and time \(B_i\) to complete the second.

The company wants to minimize the completion time of these two orders. If both orders are assigned to employee \(i\), the total time is \(A_i + B_i\); if they are assigned to employees \(i\) and \(j\) (with \(i \ne j\)), the completion time is \(\max(A_i, B_j)\).

Compute the minimum time required to complete both orders.

Input

The first line contains a positive integer \(N (2 ≤ N ≤ 1000)\), the number of employees.

Each of the next \(N\) lines contains two positive integers \(A_i, B_i (1 ≤ A_i, B_i ≤ 10^5)\), representing the time employee \(i\) requires to complete the first and second orders, respectively.

Output

Output a single integer: the minimum time required to complete both orders.

Sample Input 1

3
8 5
4 4
7 9

Sample Output 1

5

Sample Input 2

3
11 7
3 2
6 7

Sample Output 2

5

Sample Explanation

In the first sample test case, we can assign order \(1\) to employee \(2\) and order \(2\) to employee \(1\), so it takes only \(max(5, 4) = 5\) time to finish these two orders.

In the second sample test case, we can assign both orders to employee \(2\), so it takes only \(3 + 2 = 5\) time to finish these two orders.

Source

AtCoder Beginner Contest 194 B, Job Assignment

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test: about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test has a 15 second wall-clock cap; sample tests use the problem time limit, the same as the official judge
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.