P13505 [OOI 2024] Big Persimmon

Alice 和 Bob 买了一个大柿子，把它切成了 $n$ 块，每块的大小分别为 $w_1, \dots, w_n$，他们立刻开始吃起来。两个孩子会**同时**吃柿子，每个人的吃法如下： 每当某人吃完上一块（或刚开始时），他就会选择下一块开始吃。如果某块的大小为 $w$，那么吃掉它需要恰好 $w$ 秒，吃完后就可以选择新的一块。若两人同时吃完（或刚开始），则 Alice 先选第一块，但两人会同时开始吃。选择新的一块不需要时间。 由于 Alice 和 Bob 都是完美主义者，每次选块时，他们都只会从剩下的所有块中选**最小的**或**最大的**（即 $w_i$ 最小或最大的）。 吃的过程会一直持续到最后一人吃完且没有剩下的块为止。 Alice 和 Bob 都希望自己吃到的总量尽量多。请你求出，如果两人都采取最优策略，Alice 吃到的柿子总量和 Bob 吃到的柿子总量分别是多少。

第一行一个整数 $n$（$1 \le n \le 2000$），表示柿子块的数量。 第二行 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 20\,000$，$w_i \le w_{i+1}$），表示每块柿子的大小。 记 $W$ 为所有块的总大小，保证 $W \le 20\,000$。

输出一行两个整数，分别表示 Alice 和 Bob 吃到的柿子总量（都采取最优策略时）。

### 说明 在第一个样例中，Alice 应该先选一块大小为 $1$ 的柿子，然后 Bob 也选一块大小为 $1$ 的柿子。一秒后，Alice 选 $3$，Bob 选 $6$。三秒后，Alice 选 $4$。又三秒后，Bob 吃完，Alice 再过一秒吃完。此时，Alice 吃的总量为 $1+3+4=8$，Bob 吃的总量为 $1+6=7$。 在第三个样例中，Alice 先选 $1$，Bob 选 $7$。一秒后，Alice 选 $9$，再过 $6$ 秒，Bob 选 $7$。 ### 计分方式 本题共四组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。**Offline-evaluation** 表示该组结果仅在赛后可见。 | 子任务 | 分数 | 额外约束 |