P4301 [CQOI2013] New Nim Game

The traditional Nim game is as follows: There are several piles of matches, each pile has some matches (different piles may have different numbers). Two players take turns; on each turn, a player may choose one pile and remove some matches from it. They may remove just one match or the entire pile, but cannot remove matches from more than one pile. The player who takes the last match wins. This problem’s game is slightly different: On the first turn, the player may directly remove any number of whole piles. You may remove none, but you may not remove all piles. Starting from the second turn (i.e., when it is the first player’s turn again), the rules are the same as in Nim. If you move first, how can you guarantee a win? If a win is possible, you should also minimize the total number of matches taken on the first turn.

The first line contains an integer $k$, the number of piles. The second line contains $k$ integers $a_i$, the number of matches in each pile.

Output the minimum number of matches taken on the first turn. If you cannot guarantee a win, output $-1$.

Constraints For all testdata, it is guaranteed that $1 \leq k \leq 100$, $1 \leq a_i \leq 10^9$. Translated by ChatGPT 5