Choosing the Ultimate Skills

Problem Description

You must eliminate the monster that appears each day in another world for $N$ consecutive days. Each day you may use exactly one of two ultimate skills, and by the end the two skills must have been used the same number of times. You are given the power each skill consumes on each day; find the minimum total power consumption needed to finish the $N$-day task.

Input Format

The first line contains an integer $N$, the number of days. The following $N$ lines each contain two integers $s_1, s_2$ separated by a space, representing the power consumed by ultimate skill 1 and ultimate skill 2 on that day, respectively.

Output Format

Output a single line containing one integer: the minimum total power consumption.

Sample Input

4
5 4
3 6
1 8
3 9

Sample Output

14

Sample Explanation

Use ultimate skill 2 on the first and second days, and ultimate skill 1 on the third and fourth days.

Constraints

$N$ is even, $2 \le N \le 10^5$, $1 \le s_1, s_2 \le 10^6$, and all values fit within the int range.