No.698 ペアでチームを作ろう
nmnmnmnmnmnmnm問題文最終更新日: 2018-06-12 21:08:57
問題文
$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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。