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 rods for building structures. The rod has an integer length of and a value of . To prevent a catastrophe, you need to remove some rods such that no triangles of positive area can be formed using any 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?
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:
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [20%]
Subtask 4 [40%]
No additional constraints.
The first line contains a single integer , the number of building rods.
The next lines describe the rods. The line contains integers, and , indicating that the rod has a length of and a value of .
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
Sample Explanation 1
While it is possible to remove rod and fix the shipment with a cost of , it is cheaper to remove rods and , making the optimal answer .
Sample Input 2
5 1 1 3 1 2 1 6 1 4 1
Sample Output 2
Sample Explanation 2
It is optimal to remove rod for a cost of in order to make it triangle-free.