题目描述

佩奇农场养了 N个品种的猪，为了让自己的农场更加有名，他决定带小猪们参加一场重要的猪展比赛，佩奇为每个品种选择了若干头重量相同的猪参加比赛，所有品种的猪一共有 M头。

猪展评委们发现，每只猪在与其他猪一起比赛时会更加自信，因此决定将 M头猪（M为偶数）分成 M/2 对进行比赛。每一对（两只）猪都将被送到一个独立的展位中进行比赛，​所有的猪配对结束后，将同时开赛​。

在比赛中，由于每一对猪的重量差异，导致比赛时间也有差异。如果两只猪的重量分别为 Ai 和 Bi，则这对猪一起比赛需要 Ai + Bi 的时间。

请帮助佩奇农场的农场主以最佳方式将猪配对，使得所有的猪同时开赛之后，以最短的时间结束比赛。你只需要输出最短的比赛时间。

输入格式

第一行包含整数 N，表示小猪的品种数量。（1≤N≤10^5）

接下来的 N行，每行包含两个整数 Xi 和 Yi ，表示第 i 个品种的猪有 Xi 只，它们的重量均为 Yi。（1≤Yi≤10^9） 所有品种猪的总数为 M* 只，M≤10^9，且 M 为偶数。

输出格式

输出比赛最少需要的时间。

3
1 8
2 5
1 2

10

提示

【样例 1 解释】

将重量为 8 和 2 的猪配对，这对猪比赛需要的时间为 10。

将重量为 5 和 5 的猪配对，这对猪比赛需要的时间为 10。

则两个展位的比赛需要的总时间都为 10 ，因此这是最短的时间。如果进行其他配对，则有至少一个展位需要的时间比 10 长。