Ecem and Yiit are trying to decorate the blurb room and had a little disagreement. There are \(2 \cdot \mathbf{N}\) colored paintings on the wall (two paintings per each of \(\mathbf{N}\) colors). Each painting has some positive integer value.

Yiit starts picking and they alternate turns. While making a turn the person takes one of the paintings from the wall.

When there are no paintings left on the wall, if a person has both paintings of the same color one of them has to be discarded until each person has paintings of distinct colors. Then the decoration outcome is the sum of Yiit's painting values minus the sum of Ecem's painting values. Yiit tries to maximize the outcome value while Ecem's goal is to minimize it.

Your task is to find the decoration outcome provided that both players follow the optimal strategy.

Input

The first line contains the number of colors \(\mathbf{N}\) The following \(\mathbf{N}\) lines contain painting values. The \(i\)-th line contains two painting values for the \(i\)-th color.

• \(1 \le N \le 10^5\),
• \(1 \le v \le 10^9\), where \(v\) is a painting value.

Output

The decoration outcome.

Examples

Input 1:

2
7 1
10 11

Output 1:

5