No.698 ペアでチームを作ろう

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 46
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

0 ProblemId : 2251

問題文

$N$人($N$は偶数)の選手が1つのチームを組んでなんらかの戦いに挑みます。
$i$番目の選手の戦闘力は$A_i$です。

$N$人の選手はそれぞれ必ず2人のペアを組みます。
ペアを組むと戦闘力はそれぞれの選手の戦闘力の排他的論理和になります。

各ペアの戦闘力を加算した合計がチームの戦闘力になります。
最適なペアの選び方をしたときチームの最大の戦闘力はいくらか?

入力

$N$
$A_0$ $A_1$ $\dots$ $A_{N-1}$

$N$は正の整数($N$は偶数)。$2 \le N \le 14$。
$A_i$は正の整数。$1 \le A_i \le 10000000=10^7$。

出力

答えを1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4
1 2 3 4
出力
10

戦闘力1の選手と戦闘力2の選手がペアを組むとペアの戦闘力は3です。
戦闘力3の選手と戦闘力4の選手がペアを組むとペアの戦闘力は7です。
このときチームの戦闘力はペアの戦闘力を合計して10になりこれが最大です。

サンプル2
入力
2
5 6
出力
3

戦闘力5の選手と戦闘力6の選手がペアを組むと戦闘力は3です。
ペアを組むことで個々の選手の戦闘力より戦闘力が減ることがあります。
しかし、必ずペアは組まないといけません。

サンプル3
入力
10
387 137 192 123 29 193 753 210 821 437
出力
2728

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。