Brewing potion 5 - MarisaOJ: Marisa Online Judge

Brewing potion 5

Time limit: 1000 ms
Memory limit: 256 MB
Marisa has $n \times 2$ mushrooms and she wants to brew $n$ potion bottles, each using exactly 2 mushrooms. If the $i^{th}$ mushroom is paired with the $j^{th}$ mushroom, the resulting potion has a power of $A_{i,j}$. Marisa wants to find the combination of mushrooms that maximizes the total power of the $n$ potion bottles. ### Input - The first line contains an integer $n$. - The next $n \times 2$ lines, $i$-th line contains $n \times 2$ integers $A_{i, j}$. It is guaranteed that $A_{i,j}=A_{j,i}$. ### Output - Print the maximum total power of $n$ potion bottles. ### Constraints - $1 \le n \le 10$. - $0 \le |A_{i,j}| \le 10^6$. ### Example Input: ``` 1 0 -2 -2 0 ``` Output: ``` -2 ```