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?
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:
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [20%]
Subtask 4 [40%]
No additional constraints.
Input Specification
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 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 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
1
Sample Explanation 2
It is optimal to remove rod for a cost of
in order to make it triangle-free.
Comments