<PREV Problem:
NEXT>
Solved by 536 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Boxes

Time limit: 5 seconds

Petya has some empty boxes. He'd like to pack them and put some inside others and get minimal number of boxes. Help him to do it.

It's known that two boxes can't be put side by side into another box.

Box with sides x1, x2, x3, x1 >= x2 >= x3, can be put inside box with sides y1, y2, y3, y1 >= y2 >= y3, if and only if

x1 < y1, x2 < y2, x3 < y3.

Input. Input begins with number of boxes N, and N lines with box sizes follow. N < 500. Each line contains three positive integers -- box sides less than 2 000 000.

Output. Minimal number of boxes in which can be packed all others.

INPUT #1:
2
1 2 3
4 3 2
OUTPUT #1:
1
INPUT #2:
2
1 2 3
2 3 3
OUTPUT #2:
2
INPUT #3:
4
3 3 3
4 4 4
5 5 5
2 3 4
OUTPUT #3:
2

Author:
Voroztsov Artem

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75