Maximum Safe Pairing

Given (n) types of numbers. For the (i)-th type, there are (b_i) copies of the number (a_i) and each copy has a weight of (c_i). Two numbers (a_i) and (a_j) can be paired if and only if one is a multiple of the other and the ratio between the larger and the smaller number is a prime number, i.e. if (\frac{\max(a_i,a_j)}{\min(a_i,a_j)}) is prime. When a valid pair ((a_i, a_j)) is formed, it contributes a value of (c_i \times c_j) to the total. Note that a number may be used in at most one pair, and it is allowed to leave some numbers unpaired. Under the condition that the total sum of the values of the pairs is non-negative, i.e. (\sum (c_i\times c_j) \ge 0), your task is to compute the maximum number of pairs that can be formed.

A crucial observation is that a pair ((a_i, a_j)) is safe (i.e. its contribution is non-negative) if (c_i \times c_j \ge 0). In other words, pairing two positive numbers or two negative numbers results in a non-negative product; also, if at least one of the two numbers has (c=0), the product is 0. Only pairs in which one weight is positive and the other negative are unsafe. In order to keep the total value non-negative, you are allowed to select only the safe pairs.

The valid pairing condition forces that if (a_i < a_j) and (a_j) is divisible by (a_i) with (a_j/a_i) prime, then the pair ((a_i,a_j)) is allowed provided the safety condition (c_i\times c_j \ge 0) holds.

Since each type (i) has (b_i) copies, and each copy can only participate in one pair, the problem is to choose pairs (subject to the above restrictions) so that the count of pairs is maximized. This can be modeled as a bipartite matching problem on the types. To do so, sort the types in increasing order by (a_i); then any valid pairing edge always goes from a type with smaller (a_i) to a type with larger (a_i). Furthermore, assign each type a capacity of (b_i) in both the left and right partitions. A valid edge is added from type (i) (in the left partition) to type (j) (in the right partition) if (a_j \bmod a_i = 0), (a_j/a_i) is prime, and (c_i\times c_j \ge 0).

Your task is to compute the maximum flow (which corresponds to the maximum number of safe pairs) in such a network.

It is guaranteed that a solution exists which selects only safe pairs (i.e. pairs with non-negative contribution), thereby ensuring that the overall sum is non-negative.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), the number of types.\nEach of the next (n) lines contains three integers (a_i), (b_i), and (c_i), where (a_i) ((1 \le a_i \le 10^9)) is the number value, (b_i) ((1 \le b_i \le 10^9)) is the number of copies, and (c_i) (( -10^9 \le c_i \le 10^9)) is the weight of that type.

outputFormat

Output a single integer, the maximum number of pairs that can be formed such that the sum of the values of the pairs is non-negative.

sample

3
2 2 3
6 1 4
3 1 -2

1