406000: GYM102215 F Friendly Fire

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Friendly Firetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Nikita is a fan of Volvo Software games. Not so long ago this company has released a game too famous to be called.

Nikita's opponent has $$$n$$$ creatures, and the $$$i$$$-th of them has attack $$$a_i$$$ and has $$$h_i$$$ hit points. Nikita has a Friendly Fire spell. This spell is casted on two enemy creatures, and they simultaneously attack each other once. If the attacker's attack is greater or equal than the target's hit points, the target dies.

Help Nikita to choose two targets for Friendly Fire, so that the sum of attacks of all opponent's creatures will become as small as possible.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 300000$$$) — the number of the opponent's creatures.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$h_i$$$ ($$$1 \le a_i, h_i \le 10^{9}$$$) — attack and hit points of the $$$i$$$-th creature.

Output

In the first line output a single integer — the maximal possible decrease of the total attack of the opponent's creatures.

In the second line output two distinct integers from $$$1$$$ to $$$n$$$ — the numbers of creatures to cast the spell on.

If there are many possible answers, you may output any of them.

ExamplesInput
3
4 3
3 1
5 4
Output
9
3 1
Input
2
1 2
4 8
Output
1
2 1
Input
2
1 2
1 2
Output
0
1 2

加入题单

上一题 下一题 算法标签: