Minimize Delivery Cancellations

Logistics officer Byteasar is responsible for a series of delivery schedules in a city where roads form an infinite grid. The grid is defined by horizontal streets (running west‐to‐east) numbered from south to north and vertical avenues (running south‐to‐north) numbered from west to east. Every adjacent pair of streets and avenues is exactly 1 kilometer apart. Each intersection is denoted by a pair of integers \((i,j)\) representing the avenue and street indices.

Byteasar has planned n deliveries. In the i^th delivery, a truck leaves the depot at time \(t_i\) and travels at a constant speed of 1 kilometer per unit time along a fixed road. There are two types of deliveries:

• Type 1: The depot is located at \((w_i, 0)\) and the truck drives north along the avenue \(w_i\). Its position at time \(t\) (for \(t \ge t_i\)) is \((w_i, t-t_i)\).
• Type 2: The depot is located at \((0, w_i)\) and the truck drives east along the street \(w_i\). Its position at time \(t\) (for \(t \ge t_i\)) is \((t-t_i, w_i)\).

A collision may occur if a type 1 truck and a type 2 truck are at the same intersection at the same time. In particular, let a type 1 delivery start with parameters \(t_1\) and \(w_1\) and a type 2 delivery start with parameters \(t_2\) and \(w_2\). Their paths intersect at time \(t\) if and only if:

[ \begin{cases} w_1 = t - t_2,\ t - t_1 = w_2, \end{cases} ]

which implies \(t = t_1 + w_2\) and the collision condition becomes:

[ t_2 = t_1 + w_2 - w_1. ]

Observing the equations, we notice that a collision between a type 1 and a type 2 truck happens if and only if they share the same value of \(t - w\). To avoid any collisions, Byteasar may cancel some deliveries. For each unique key defined as \(key = t_i - w_i\), if both types of deliveries are present, a collision would occur. Therefore, Byteasar must cancel all deliveries from one type in that group. To minimize cancellations, for each key he should keep the group with the larger count and cancel the other group.

Your task is to determine the minimum number of delivery plans to cancel so that no collision ever occurs.

inputFormat

The first line contains an integer \(n\) (\(1 \le n\le\) appropriate limit) representing the number of deliveries scheduled.

Each of the following \(n\) lines contains three integers \(d\), \(t_i\), and \(w_i\):

• If \(d = 1\), the delivery is of Type 1 with depot at \((w_i,0)\) and the truck will move north.
• If \(d = 2\), the delivery is of Type 2 with depot at \((0,w_i)\) and the truck will move east.

It is guaranteed that at any time, each depot dispatches at most one truck.

outputFormat

Output a single integer --- the minimum number of delivery plans that must be cancelled to ensure that no collision occurs.

sample

3
1 2 1
2 3 2
1 5 1

1