410082: GYM103938 J Quantum Chaos

UT's Quantum Collective is hosting their annual qubit selection party! Each year, the members come together to select their very favorite qubits to showcase to the rest of the university. Each qubit, $$$|\varphi\rangle$$$ can be written in the form $$$|\varphi\rangle = \alpha|0\rangle + \beta|1\rangle$$$ for integers (for some reason, the collective banned complex numbers many years ago) numbers $$$\alpha, \beta$$$. This is analogous to saying that every qubit has some "$$$|0\rangle$$$" component and some "$$$|1\rangle$$$" component. Sometimes this can be expressed shorthand by $$$|\varphi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$$$ (a column vector) where $$$|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$$ and $$$|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$$.

The Quantum Collective did an initial pruning, and now they are down to the top $$$n$$$ qubits in the world. Now all that is left to do is rank them! The members of the quantum collective will select a ranking for each qubit, starting with the very best and ending with the very worst (the $$$n$$$th place qubit).

However, every possible ranking that can be assigned to the qubits has a score associated with it. The score of a ranking is calculated at each step of the ranking. First off, the first qubit, $$$|\varphi_1\rangle$$$ contributes $$$\alpha_1 + n \cdot \beta_1$$$ to the score. Then, the following recurrence relation applies: assuming that $$$k$$$ qubits have been selected so far (for $$$1 \leq k < n$$$), the $$$k + 1$$$th qubit contributes $$$\sum_{i=1}^k{\alpha_i \cdot \alpha_{k+1} \cdot k + \beta_i \cdot \beta_{k+1} \cdot (n - k)}$$$ to the score (where each of the $$$k$$$ previously chosen qubits is denoted by its column vector coefficients).

Based on the formula for score calculation, can you determine the highest score that the collective can achieve by choosing their ranking of qubits optimally?

The input will begin with a line containing a single integer, $$$n \ (1 \leq n \leq 20)$$$, the number of qubits that must be ranked. The next $$$n$$$ lines will each consist of two space-separated integers, $$$\alpha$$$ and $$$\beta\ (1 \leq \alpha, \beta, \leq 1000)$$$, respectively, denoting the state of each qubit.

The output should consist of a single integer denoting the highest score that the collective can possibly achieve by choosing the optimal ranking of qubits.

3
1 1
2 2
3 3

45

6
1 2
6 7
3 8
4 2
9 9
1 1

1850