This problem was featured from DMOJ's Wesley Anger Contest 3 and has been transferred to this site. The updated time limit has been multiplied by a factor of 3. If there are any concerns regarding a specific problem's time limit, please contact the administrators.

In a parallel universe, the least important data structure in computer science is the triangle. In fact, it is widely frowned upon to have a triangle in any way, shape, or form. As you are reading this the problem author is being locked up behind bars for mentioning the forbidden shape.

You were recently given a shipment of \(N\) rods for building structures. The \(i^{th}\) rod has an integer length of \(l_i\) and a value of \(v_i\). To prevent a catastrophe, you need to remove some rods such that no triangles of positive area can be formed using any \(3\) of the remaining rods. Not wanting your money to go to waste, what is the minimum sum of values of the removed rods used to prevent a catastrophe?

Constraints

For this question, Python users are recommended to use PYPY over CPython.

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

\(1 \le N \le 5\,000\)
\(1 \le l_i \le 10^9\)
\(1 \le v_i \le 10^9\)

Subtask 1 [10%]

\(1 \le N \le 15\)

Subtask 2 [30%]

\(1 \le N \le 400\)

Subtask 3 [20%]

\(v_i = 1\)

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains a single integer \(N\), the number of building rods.

The next \(N\) lines describe the rods. The \(i^{th}\) line contains \(2\) integers, \(l_i\) and \(v_i\), indicating that the \(i^{th}\) rod has a length of \(l_i\) and a value of \(v_i\).

Output Specification

Output an integer, the minimum sum of values of the removed rods used to prevent a catastrophe.

Sample Input 1

5
7 9
1 1
3 5
9 2
5 3

Sample Output 1

5

Sample Explanation 1

While it is possible to remove rod \(1\) and fix the shipment with a cost of \(9\), it is cheaper to remove rods \(4\) and \(5\), making the optimal answer \(2 + 3 = 5\).

Sample Input 2

5
1 1
3 1
2 1
6 1
4 1

Sample Output 2

1

Sample Explanation 2

It is optimal to remove rod \(5\) for a cost of \(1\) in order to make it triangle-free.