3143: 击鼓传花
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：0
题目描述
小爱和小艾在玩一个游戏，每个人的游戏目标是为自己夺取尽量多的分数。游戏一共有 �n 轮，每一轮游戏都对应一个分数，分数在游戏开始前就是给定的，记为 �1,�2,⋯,��a1,a2,⋯,an。
每一轮游戏中，手上有花的人可以做出选择：
- 她可以选择保留花。这样，这轮的分数就会送给对方，而到下一轮的时候，花仍在自己手上；
- 她可以选择取走这一轮的分数。这样，到下一轮的时候，花就是对方的，但这一轮的分数就是自己的；
游戏开始前，花在小爱手里。若双方都会使用最佳策略去尽量多得获得分数，那么小爱可以多少分数呢？
输入
第一行：单个整数 �n
第二行：�n 个整数 �1,�2,…,��a1,a2,…,an
第二行：�n 个整数 �1,�2,…,��a1,a2,…,an
- 对于 30%30% 的数据，保证 1≤�≤501≤n≤50；
- 对于 60%60% 的数据，保证 1≤�≤50001≤n≤5000；
- 对于 100%100% 的数据，保证 1≤�≤200,0001≤n≤200,000；
- 1≤��≤100001≤ai≤10000；
输出
单个整数：表示小爱获得的最大分数
样例输入 复制
4
5 2 7 3样例输出 复制
10