题目描述

爱丽丝和鲍勃买了一个大柿子，将其切成 $n$ 块，块的大小分别为 $w_1, \dots, w_n$，并立刻开始食用。他们将同时吃这些块，食用过程如下所述：

每当某人吃完前一块（或在开始用餐时），他们会选择下一块并开始食用。如果选择了一块大小为 $w$ 的柿子块，食用它将花费恰好 $w$ 秒，之后他们会再次选择新的一块。如果两人同时吃完前一块（或在用餐开始时），则爱丽丝优先选择，但两人将同时开始食用新的一块。选择新的一块不花费时间。

由于爱丽丝和鲍勃都是完美主义者，他们在选择块时，会从剩余的块中挑选最小（$w_i$ 最小）或最大（$w_i$ 最大）的一块。

食用过程在最后一人吃完自己的块时结束。

爱丽丝和鲍勃都希望尽可能多地吃到柿子。计算如果他们都以最优方式选择块，爱丽丝和鲍勃各自吃到的块的总大小。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 2000)$，表示柿子的块数。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ $(1 \leq w_i \leq 20000, w_i \leq w_{i+1})$，表示柿子块的大小。

设 $W$ 为所有块大小的总和。保证 $W \leq 20000$。

输出格式

在一行中输出两个整数，分别是爱丽丝和鲍勃在都以最优方式选择块时吃到的块的总大小。

5
1 1 3 4 6

8 7

4
1 1 2 2

3 3

4
1 7 7 9

10 14

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。