#1002. B. 说服合伙人

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

构建成功初始模型后,你需要寻找一位可以完全信赖,又志趣相投的合伙人,你的好兄弟cyy是你最好的选择。但你需要说服他,于是你决定通过你们经常一起玩的打牌游戏来赢得他的加盟。

高呼三声csfnb后csf和cyy开始打牌。

和一般的牌不同,他们打的牌上面有两个点数,分别设为 。如果csf获得这张牌,他会获得 点分数;如果 cyy获得这张牌,他会获得 点分数。

游戏开始后csf和cyy轮流从牌堆里拿牌,csf先手,直到牌堆的牌被拿完时游戏结束。csf的策略很简单,他每次选牌堆里 最大的那张牌据为己有,如果同时有多张牌有同样的 ,那么他会取 最大的那一张。现在cyy想知道他可以获得的最大的分数。

输入格式

第一行一个正整数 ,表示一开始有 张牌。

接下来 行,第 行两个整数 ,表示第 张牌的点数。

输出格式

一行一个整数,表示cyy按最优策略取的话,可以获得的最大分数。

样例

样例输入1

1
1 23333

样例输出1

0

样例输入2

2
1 23333
2 1

样例输出2

23333

样例输入3

3
1 23333
2 1
3 1

样例输出3

23333

数据范围与提示