#2714 상 도 덕

1 s   128 MB  

Description

한 변의 길이가 N(<=50)인 정육면체 형태의 동물사육장이 있다.

이 곳에 여러 종류의 동물들을 풀어 놓는다.

이 동물들은 처음 자신들이 놓인 자리에서 시작해서 영역을 확장해 간다.

모든 동물의 이동 속도는 단위 시간당 한칸이며 6방향으로 움직일 수 있다.

같은 층에서 상하좌우 칸과 바로 윗층 아랫층으로 총 6방향이다.

모든 동물은 한 종류당 한 마리씩만 주어진다.

동물들의 좌표와 함께 동물들의 힘도 주어진다.

당연히 사자는 토끼보다 쎄다.

하지만 모든 동물들은 상도덕이란 것이있어서 먼저 칸을 점유한 동물이 있으면 양보한다.

다만 특정 칸에 여러 종류 동물이 동시에 도착할 경우 힘이 센 동물이 그 영역을 차지한다. 

Input

첫째줄에 테스트케이스 T(<=30)가 주어진다.

다음 줄에 N과 동물의 수 M이 주어진다.

다음 M줄에 각 동물의 x y z좌표와 힘, 총 4개의 값이 각 줄에 주어진다.

단, 좌표는 양수이다. 한 칸에는 한 마리의 동물만 주어진다.

모든 동물의 힘은 다르다. 또한 힘은 100이하이다.

Output

각 케이스별로 동물들의 영역점유하기가 모두 끝났을때
 
제일 많은 영역을 점유한 동물이 차지한 영역의 수를 출력한다.

Sample Input

Sample Output

1
10 5
1 1 1 10
1 3 5 9
4 5 5 20
3 4 4 7
2 3 4 5
#1 500

Source

Sink
Submit Status Discuss