Shark Dinner

Time limit2sMemory limit128 MB

Summary

Given each shark's size, speed and intelligence, model who can eat whom (at most two meals, at most one death each) as a flow network and find the minimum number of survivors.

Level: Hard8 of 10
Topics: Graph, BFS, Greedy
Solved: No attempts yet

Problem

There are N sharks. For each shark, three numbers describe its size, speed, and intelligence.

Shark A can eat shark B if A's size, speed, and intelligence are each greater than or equal to B's corresponding values. To prevent too many sharks from disappearing, each shark may eat at most two other sharks.

Only one eating action happens at a time. A shark that has already been eaten cannot eat another shark later.

Given the size, speed, and intelligence of all N sharks, find the minimum possible number of sharks that can survive.

Input

The first line contains the number of sharks N. N is a positive integer not greater than 50.

Each of the next N lines contains three positive integers: the shark's size, speed, and intelligence. Each value is not greater than 2,000,000,000.

Output

Print the minimum possible number of surviving sharks.

Examples4

Example 1
Input
```
5
4 5 5
10 10 8
5 7 10
8 7 7
8 10 3
```
Expected output
```
2
```
Example 2
Input
```
3
1 2 1
4 3 5
3 1 2
```
Expected output
```
1
```

Example 3

Input

5
1 4 2
2 3 4
3 2 1
4 1 3
100 100 100

Expected output

Example 4
Input
```
4
4 3 8
4 3 8
4 3 8
4 3 8
```
Expected output
```
1
```