Ilya 按照以下规则玩纸牌游戏。
玩家拥有多张牌。每张卡片都包含两个非负整数,一个位于卡片的顶部,一个位于卡片的底部。在回合开始时,玩家选择一张牌来玩。如果牌的顶部包含数字ai,底部包含数字bi,那么当玩家打牌时,他获得ai点,并且还获得打出额外bi牌的机会。玩完后,该牌将被丢弃。
更正式地说:假设有一个可以打出的牌的计数器。在回合开始时,计数器等于 1。当打出一张牌时,计数器会因打出的牌而减一,并增加写在牌底部的数字bi。然后打出的牌将被丢弃。如果此后计数器不等于零,则玩家有机会从剩余的牌中打出另一张牌。当计数器归零或玩家用完牌时,该轮结束。
当然,伊利亚想要获得尽可能多的积分。如果你知道他的牌,你能确定他能得到的最大分数吗?
输入
第一行包含一个整数 n (1 ≤ n ≤ 1000) — Ilya 拥有的牌数。
接下来的 n 行中的每一行都包含两个非负的空格分隔整数 — ai 和 bi (0 ≤ ai, bi ≤ 104) — 数字,分别写在第 i 张卡片的顶部和底部。
输出
打印单个数字 — 根据所描述的规则,您在一轮中可以获得的最大分数。
示例
输入 #1
2 1 0 2 0
输出 #1
2
输入 #2
3 1 0 2 0 0 2
输出 #2
3
注意
在第一个示例中,两张牌都没有带来额外的步数,因此您应该玩能带来更多分数的牌。
在第二个示例中,您应该首先打出第三张牌,该牌不会带来任何分数,但可以让您打出剩余的两张牌。