Problem K
バラバラ問題

Picture by gratuit via Freeimageslive.

アリスとボブは、新しい整数を手に入れて、カクテルパーティでそれを他のカップルに披露した後、よく眠るために家に向かいました。その整数がかなり大きかったので、彼らは一緒にそれを運ばざるを得ませんでした。その時、ベイズ湾の右の、ブール大通りを災害が襲いました。$2$ 人のどちらが最初につまづいたのかわかりませんが、彼らはつまづきました。そして彼らの前の道路で、それらの整数は $n$ 個の正の整数のピースに粉々に砕けました。

すでに高価な整数の取得のための財政的なストレス下にあった、このカップルの結婚は、この事件を乗り越えることができませんした。そして、ボブとアリスは分かれることを決心しました。そのため、どのように残った整数を分割するのかが問題となりました。ボブとアリスは、残りの $n$ 個のピースでゲームをプレイすることを決めました: $２$ 人は何も残らなくなるまで何度も、交互に交代でピースを選択します。

ボブとアリスは、共にとても利益を得たいので、出来るだけ整数の合計が最大になるように取得しようとします。それぞれの終わる整数の値を計算してください。両方のプレイヤーが最適にプレイすると仮定します。A がアルファベット順で B の前に来るので、アリスが最初に動きます。

入力

入力は2行で構成されます。

• $1 \leq n \leq 15$の単一の整数、ピースの数。

• スペースで区切られた $a_0, a_1, \dots , a_{n-1}$のピースの値。これは $1 \leq a_ i \leq 100$で与えられる。

出力

$2$つの整数を含む$1$行の出力、アリスのピースの値の合計とボブのピースの値の合計

3
3 1 2

4 2

4
1 2 2 1

3 3