1778 - 取数游戏
描述

给定一个包含 N 个正整数的数列  {An},小 A和小B 两人轮流进行取数游戏。

小 A 先手,每一轮一人从数列中选取一个数并将这个数从数列中删掉,如果小 A 选择的数是偶数,则小 A 的得分加上这个数,否则小 A 不加分;

如果小 B 选择的数是奇数,则小 B 的得分加上这个数,否则小 B 不加分。

假设二人都采取最优策略,最后得分高的获胜,请输出获胜者,如果平局则需指明。


输入

第一行,一个正整数N,输入数据保证1≤N≤100。

第二行,从左至右给出了游戏初始时的N个正整数。这  些正整数保证不超过200。


输出

 一行,输出两个用空格隔开的正整数。他们分别表示游戏的先取者在最坏情况下最高的得分和此时后取者的得分。

样例

输入

6
4 7 2 9 5 2

输出

18 11
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1