题目描述

给定 $n$ 个二元组 $a_i,b_i$，表示可重集中 $S$ 有 $b_i$ 个 $a_i$。

定义编码树为一棵叶节点个数恰好为 $|S|$ 的满二叉树 $T$，每个叶节点有权值，$|S|$ 个权值与 $S$ 中元素一一对应。

定义编码树的总权值为 $\sum\limits_{u\in\text{leaf}} dep_u\cdot w_u$，其中 $\text{leaf}$ 为所有叶节点，$dep_u$ 为 $u$ 的深度（根的深度为 $0$），$w_u$ 为 $u$ 的权值。

定义哈夫曼树为总权值最小的编码树。

求哈夫曼树总权值。

输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，每行两个整数 $a_i,b_i$。

输出格式

一行，一个整数，表示答案。

样例

样例输入 1

3
1 3
2 2
3 1

样例输出 1

25

数据范围

对于 $100\%$ 的数据，$1\le n,a_i,b_i\le 2\times 10^5$，$a_i$ 互不相同。

$\text{Subtask 1}(30\%):\sum b_i\le 1000$。

$\text{Subtask 2}(30\%):\sum b_i\le 2\times 10^5$。

$\text{Subtask 3}(20\%):n\le 1000$。

$\text{Subtask 4}(20\%):$ 无特殊限制。