99032 - 猴子拆房

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

输入

输入共 n+1 行。 第 1 行一个整数 n,表示猴村里原有的房屋数量。 接下来 n 行,其中第 i+1 行两个整数h_{i}c_{i},分别表示第 i 幢房屋的高度和拆除第 i 幢 房屋需要支付给工人的费用。

输出

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

样例

输入

2 
2 3 
4 5 

输出

3 

输入

3 
2 4 
2 5 
1 3 

输出

0 

输入

6 
3 5 
3 4 
1 7 
1 7 
4 2 
4 1

输出

10 

提示

30%的数据,1≤n≤100,1≤h_{i}≤500,1≤c_{i}≤100。 100%的数据,1≤n≤ 10^5 ,1≤h_{i}10^5 ,1≤c_{i}≤500。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题