Background

Special for beginners, ^_^

Description

小爱拿到了n张卡片，每张卡片的正反面均写有一个数字，其中第i卡片的正面的数字为$a_i$，反面的数字为$b_i$​。

他想把每张卡片选取合适的一面后，放入下列算式中(算式中一半加数，另一半减数)，卡片之间顺序可以交换，但每张卡片只能用一次。.

请问，小爱通过以上操作，能得到的最大值是多少？

Format

Input

第一行，一个正整数n（$\le 1048576$的偶数）。

接下来n行，每行两个整数$a_i、b_i$，每个整数的绝对值不超过$10^9$。 .

Output

输出共一行，一个整数，表示填入算式后，所能获得的最大值。

Samples

6
10 -12
-17 -7
-7 5
-17 2
-4 3
-10 -8

62

Limitation

1s, 1024KiB for each test case.