Pilot Crews

Time limit1sMemory limit128 MB

Summary
Given pilots sorted by age with captain and assistant salaries, pair them into captain-older-than-assistant crews minimizing total salary paid.
Level

Medium7 of 10

Topics
Greedy, Sorting, Dynamic programming
Solved
No attempts yet

Problem

Charlie runs an airline transport company. The company has N pilots, where N is even, and he must form exactly N/2 crews.

Each crew consists of two pilots: one captain and one assistant. The captain must be older than the assistant.

For each pilot, the contract lists two possible salaries: X_i if the pilot works as a captain and Y_i if the pilot works as an assistant. For the same pilot, the captain salary is always larger than the assistant salary. However, an assistant in one crew may still earn more than that crew's captain.

Choose a valid role for every pilot and form the crews so that the total salary paid by the company is as small as possible.

Input

The first line contains an even integer N (2 <= N <= 10000), the number of pilots.

Each of the next N lines contains two integers X_i and Y_i (1 <= Y_i < X_i <= 100000). X_i is the salary if the pilot is a captain, and Y_i is the salary if the pilot is an assistant.

The pilots are listed in increasing order of age, from the youngest pilot to the oldest pilot.

Output

Print one integer: the minimum total salary needed to form all crews.

Examples3

  1. Example 1

    Input
    4
5000 3000
6000 2000
8000 1000
9000 6000
    Expected output
    19000

  2. Example 2

    Input
    6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000
    Expected output
    32000

  3. Example 3

    Input
    6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000
    Expected output
    33000