99032 - 猴子拆房

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

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

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

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。