Pilot Crews

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.

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.

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