Given $n$ pairs $(a_i, b_i)$, representing that the multiset $S$ contains $b_i$ occurrences of $a_i$.
An encoding tree is defined as a full binary tree $T$ with exactly $|S|$ leaf nodes, where each leaf node is assigned a weight, and the $|S|$ weights correspond one-to-one with the elements in $S$.
The total weight of an encoding tree is defined as $\sum\limits_{u\in\text{leaf}} dep_u\cdot w_u$, where $\text{leaf}$ is the set of all leaf nodes, $dep_u$ is the depth of $u$ (the depth of the root is $0$), and $w_u$ is the weight of $u$.
A Huffman tree is defined as an encoding tree with the minimum total weight.
Calculate the total weight of the Huffman tree.
Input
The first line contains an integer $n$.
The next $n$ lines each contain two integers $a_i$ and $b_i$.
Output
A single integer representing the answer.
Examples
Input 1
3 1 3 2 2 3 1
Output 1
25
Constraints
For $100\%$ of the data, $1\le n, a_i, b_i \le 2\times 10^5$, and all $a_i$ are distinct.
Subtasks:
- Subtask 1 ($30\%$): $\sum b_i \le 1000$.
- Subtask 2 ($30\%$): $\sum b_i \le 2\times 10^5$.
- Subtask 3 ($20\%$): $n \le 1000$.
- Subtask 4 ($20\%$): No special restrictions.