题目描述

猴村经过多年的发展与建设，村里面高楼林立，但为了环境整治，让村子里的房子与猴山上的环境更加和谐，猴子们打算拆掉一些房子。猴子们对拆房工人提出的拆房要求是：拆房后猴村里最高房屋的数量超过其他高度房屋数量之和，即最高房屋的数量超过房屋总数的一半。拆房的过程中，由于每幢房子结构和强度不同，需要支付给工人的钱也可能是不同的。
猴子们希望用最少的钱来满足拆房要求。特殊情况说明：当村里只剩一间房屋或者剩几间高度一样的房屋时，也算是满足拆房要求，不需要拆除。

格式

输入格式

输入共 \(n+1\) 行。

第 \(1\) 行一个整数 \(n\)，表示猴村里原有的房屋数量。

接下来 \(n\) 行，其中第 \(i+1\) 行两个整数 \(h_i\) 和 \(c_i\)，分别表示第 \(i\) 幢房屋的高度和拆除第 \(i\) 幢房屋需要支付给工人的费用。

输出格式

输出一行,一个整数,表示满足拆房要求所需支付的最小费用。

样例1

样例输入1

2
2 3
4 5

样例输出1

3

样例解释

样例中共有 \(2\) 幢房屋，第 \(1\) 幢房屋的高度为 \(2\)，拆房费用为 \(3\)，第 \(2\) 幢房屋高度为 \(4\)，拆房费用为 \(5\)。拆除第 \(1\) 幢后满足拆房要求，所需支付的费用为 \(3\)。

限制

\(100\%\)的数据：\(1≤n≤10^5，1≤h_i≤10^5，1≤c_i≤500\)。