题目描述

Oni 喜欢用积木搭高塔，但她的父母实在受不了高塔倒塌时的噪声和满地积木。于是妈妈想了一个新游戏：不用真实积木，而是把二维矩形纸片贴在墙上的板子上，拼成一座“塔”。

每个矩形都有两条边，长度分别为 $s$ 和 $t$。放置时可以选择任意一种朝向：

• 让长度为 $s$ 的边作为水平边；
• 或者让长度为 $t$ 的边作为水平边。

每个矩形必须恰好放在另一个矩形的正上方，或者放在地面线上。若一个矩形放在另一个矩形正上方，则上方矩形的水平边长度必须严格小于下方矩形的水平边长度。整座塔必须恰好有一个矩形放在地面线上。

妈妈保证存在一种方法，可以把所有 $n$ 个矩形都用在同一座塔中。

现在请你选择每个矩形的朝向，并决定它们从下到上的顺序，使得在所有矩形都使用的前提下，塔的总高度最大。

输入格式

第一行包含一个整数 $n$，表示矩形数量。

接下来 $n$ 行，每行包含两个整数 $s,t$，表示一个矩形的两条边长。

数据保证：

• $1\le n\le 250000$；
• $1\le s\le t\le 10^9$；
• 单位为 nm；
• 保证存在一种使用所有矩形搭成合法塔的方案。

输出格式

输出一行一个整数，表示在所有矩形都使用且从下到上水平边严格递减的条件下，能够得到的最大总高度，单位为 nm。

样例输入 #1

3
50000 160000
50000 100000
50000 100000

样例输出 #1

200000