题目描述

关羽接到了刘备的命令，在给定的n个敌军城池当中(城池在一条直线上，例如从第一个城池到第三个城池必须经过第二个城池)选择若干个地理位置相邻的城池去攻打。给定每个城池的奖励值(正数表示攻下城池可以获得的俘虏数，负数表示己方士兵的损失数)以及每个城池和关羽营地的距离，徐老师穿越到三国时期，帮助关羽出谋划策，选择攻打哪些城池才可以获得最大的奖励值(至少要攻打一座城池)，如果不同方案获得的奖励值相同则优先选择最近的城池，满足上述条件的情况下，选择的城池数越少越好。

输入格式

输入第一行，包含一个正整数 n，表示一条直线上共有n座城池。1≤n≤30000

接下来 n 行，每行两个整数vi，di,分别表示第i个城池的奖励值和关羽营地与该城池的距离

-${10}^4$≤vi≤${10}^4$,1≤di≤30000

数据保证每个城池与关羽营地的距离不同

输出格式

输出共两行

第一行一个数字表示最大奖励值

第二行一组数字用空格隔开，按照升序输出每个被选择的城池与关羽营地的距离。

样例

样例输入

5
5 1
3 3
-3 5
-8 2
5 4

样例输出

8
3 4