Minimizing the Card Frame Expression

You are given n cards. Each card has two numbers (one on each side). You are also given an expression frame where each card will be placed. The frame is formed by boxes (denoted as "O") interleaved with arithmetic operators '+' and '-' as shown below.

For example, when n = 8, the frame is:

-O+O-O+O-O+O-O+O

This indicates that the first card is preceded by a '-' sign, the second by a '+' sign, the third by a '-' sign, and so on. In general, if you number the positions from 1 to n, the sign for the i-th card is given by:

$$ s_i = \begin{cases} -1, & \text{if } i \text{ is odd}\\ +1, & \text{if } i \text{ is even} \end{cases} $$

Your task is to fill the cards into the frame (you may reorder the cards arbitrarily) and choose a side from each card (note that the digit 6 cannot be used as 9 and vice versa) so that the final computed result is minimized. When a card is placed in a position with sign s, you must use the corresponding digit according to the following strategy:

• If placed in a position with a negative sign (i.e. s = -1), you want to use the larger digit from that card (to subtract as much as possible).
• If placed in a position with a positive sign (i.e. s = +1), you want to use the smaller digit from that card (to add as little as possible).

Thus, if for a given card the two digits are \(a\) and \(b\) (with \(\min(a,b)\) and \(\max(a,b)\) defined accordingly), then:

• If the card is placed in a negative position, its contribution is \(-\max(a,b)\).
• If it is placed in a positive position, its contribution is \(\min(a,b)\).

You must assign exactly \(\lceil n/2 \rceil\) cards to negative positions (corresponding to the odd positions in the frame) and the remaining to positive positions. The challenge is to select an assignment (i.e. a permutation of the cards) and decide for each card which side to use in order to minimize the expression:

$$ \text{Result} = \sum_{i=1}^{n} s_i \times \text{(chosen digit from card } i\text{)}. $$

Input: The first line contains an integer n. The following n lines each contain two integers representing the two digits on a card.

Output: Output a single integer which is the minimum possible value of the expression.

inputFormat

The input begins with an integer n (n ≥ 1), representing the number of cards. The next n lines each contain two space-separated integers, describing the numbers on the two sides of each card. Note that the digit 6 cannot be treated as 9 and vice versa.

outputFormat

Output a single integer — the minimum value obtainable by optimally arranging the cards in the frame and choosing the appropriate side for each card as described.

sample

2
1 2
2 3

-2