Oni 喜欢用积木搭高塔。但她的父母对此并不怎么高兴。每当塔倒塌时发出的刺耳噪音，以及不得不一直从地板上捡起积木，都让他们快要疯了。有一天，Oni 的母亲想到了一个主意。与其用实体的积木搭塔，为什么不让 Oni 用二维矩形在墙上的板子上拼出一座塔的图案呢？Oni 的母亲剪出了各种大小和颜色的矩形，在板子的底部画了一条代表地面的水平线，并向 Oni 解释了游戏的规则：每个矩形必须放置在另一个矩形的正上方或地面线上。对于每个矩形，你可以选择它的两种摆放方向之一。也就是说，如果一个矩形的边长为 $s$ 和 $t$，你可以选择将长度为 $s$ 的边水平放置，或者将长度为 $t$ 的边水平放置。如果一个矩形的水平边长严格小于其下方矩形的水平边长，你就可以将它放置在那个矩形的正上方。必须恰好有一个矩形放置在地面线上。现在，试着搭出一座尽可能高的塔吧！

Photo by Matt Schilder on flickr, cc by-sa

Oni 的母亲特意确保了使用所有矩形搭出一座塔是可行的，以免打击 Oni 的积极性。但 Oni 当然很快就失去了兴趣，又回去玩她的实体积木了。毕竟，如果感受不到塔倒塌前那种悬念，搭塔又有什么意义呢？而她的父亲却对妻子的这个谜题产生了兴趣，因为他意识到这并不是一个儿童游戏。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 250\,000$)，表示矩形的数量。接下来 $n$ 行，每行包含两个整数 $s$ 和 $t$ ($1 \le s \le t \le 10^9$ nm)，表示一个矩形的尺寸。

你可以确信一定存在一种使用所有 $n$ 个矩形搭成一座塔的方法。

输出格式

输出一行，包含使用所有矩形搭成的最高塔的高度（单位为 nm），要求从下到上水平边长严格递减。

样例

输入格式 1

3
50000 160000
50000 100000
50000 100000

输出格式 1

200000