A - カードと兄妹 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 枚のカードがあり、i (1 ≦ i ≦ N) 枚目のカードには整数 A_i が書かれています。ゲーム好きの兄妹はこれらのカードを使ってゲームをしようとしています。

  • 最初に全てのカードを、カードに書かれた整数が見えるようにテーブルの上に並べる。
  • プレイヤーは自分のターンに、テーブルの上にあるカードからちょうど 1 枚のカードを選んで取る。
  • テーブルの上にカードがなくなるまで、交互にターンを繰り返す。
  • 最終的に、自分が取ったカードに書かれた整数の和がプレイヤーの スコア となる。

2 人ともが自分のスコアを出来るだけ大きくしようとしたとき、先手のスコアはいくつになるでしょうか？

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N
  • 1 行目には、カードの枚数を表す整数 N (1 ≦ N ≦ 1000) が与えられる。
  • 2 行目には、各カードに書かれた整数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ 1000) は、i 枚目のカードに書かれた整数を表す。

出力

先手のスコアを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2
400 628

出力例1

628

この例では、ゲームは以下のように進行します。

  • 先手が 2 枚目のカードを取る。
  • 後手が 1 枚目のカードを取る。

このとき、先手のスコアは 628 となり、後手のスコアは 400 となります。

入力例2

5
2 5 9 6 5

出力例2

16

この例では、ゲームは以下のように進行します。

  • 先手が 3 枚目のカードを取る。
  • 後手が 4 枚目のカードを取る。
  • 先手が 2 枚目のカードを取る。
  • 後手が 5 枚目のカードを取る。
  • 先手が 1 枚目のカードを取る。

このとき、先手のスコアは 16 となり、後手のスコアは 11 となります。