P7891 [入门赛 #10] Coin Selection G（hard version）

Farmer John 和 Bessie 正在一起玩硬币选择游戏。 初始时桌面上有 $n$ 枚硬币，每枚硬币有一个面额，我们使用 $a _ 1, a _ 2, \cdots, a _ n$ 分别代表第 $1, 2, \cdots, n$ 枚硬币的面额。 他们还各有一个属于自己的钱包，初始时，钱包都是空的。 从 **Bessie** 开始，双方轮流操作。每次操作中，当前的操作者会从桌面上剩余的硬币中选择**面值不超过当前自己钱包中硬币的总面额**的硬币中**面额最大的**一枚硬币，把它从桌子上拿走，放到自己的钱包里。如果桌面上剩余的**所有**硬币面值都**超过了自己钱包里已有硬币的总面额**，那么选择剩余的所有硬币中面额**最小**的一个。 当桌面上没有硬币时，游戏结束。 请你分别求出， 游戏结束后，Farmer John 和 Bessie 钱包里硬币的总面额。

第一行为一个整数，代表初始时桌面上的硬币的数量 $n$。 第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，分别代表第 $1, 2, \cdots, n$ 枚硬币的面额。

输出一行两个整数，第一个整数表示 Bessie 最终钱包里硬币的总面额，第二个整数表示 Farmer John 最终钱包里的总面额。

### 数据规模与约定 - 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^{9}$。 Provider：一扶苏一