Problem Description

To the west of the Australian continent, there is a vast Indian Ocean. JOI, a marine researcher, is studying the properties of certain species of fish that inhabit the Indian Ocean.

For each species of fish, a cuboid habitat range is defined in the sea. Fish can move to any location within their habitat range, including the boundaries, but never move outside it. A point in the sea is represented by three real numbers \( (x, y, d) \): \( (x, y, d) \) represents a point that is \( x \) units east and \( y \) units north from a reference point when viewed from above, and \( d \) units deep from the sea surface. The sea surface is assumed to be flat.

JOI wants to know how much of the sea is occupied by the overlapping habitat ranges of at least \( K \) species of fish. Create a program to calculate the total volume of such overlapping areas.

Input Format

The input consists of \( 1 + N \) lines.

The first line contains two integers \( N, K \) \( (1 \leq K \leq N \leq 50) \), indicating that there are \( N \) species of fish and JOI is interested in the volume of areas where the habitat ranges of at least \( K \) species overlap.

The following \( N \) lines each contain six integers \( X_{i,1}, Y_{i,1}, D_{i,1}, X_{i,2}, Y_{i,2}, D_{i,2} \) \( (0 \leq X_{i,1} < X_{i,2} \leq 1,000,000 (= 10^6), 0 \leq Y_{i,1} < Y_{i,2} \leq 1,000,000 (= 10^6), 0 \leq D_{i,1} < D_{i,2} \leq 1,000,000 (= 10^6)) \). These represent that the habitat range of the \( i \)-th species of fish is a cuboid with vertices at \( (X_{i,1}, Y_{i,1}, D_{i,1}) \), \( (X_{i,2}, Y_{i,1}, D_{i,1}) \), \( (X_{i,2}, Y_{i,2}, D_{i,1}) \), \( (X_{i,1}, Y_{i,2}, D_{i,1}) \), \( (X_{i,1}, Y_{i,1}, D_{i,2}) \), \( (X_{i,2}, Y_{i,1}, D_{i,2}) \), \( (X_{i,2}, Y_{i,2}, D_{i,2}) \), \( (X_{i,1}, Y_{i,2}, D_{i,2}) \).

Output Format

Output the total volume of the areas where the habitat ranges of at least \( K \) species of fish overlap in one line.

Sample Input and Output

Sample Input #1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

Sample Output #1

49000

Sample Input #2

1 1
0 0 0 1000000 1000000 1000000

Sample Output #2

1000000000000000000

Notes/Hints

Sample Explanation 1

In Sample Input #1, for example, the point \( (45, 65, 65) \) is within the habitat ranges of the 1st and 3rd species of fish, so it satisfies the condition. On the other hand, the point \( (25, 35, 45) \) is only within the habitat range of the 2nd species of fish, so it does not satisfy the condition. The habitat ranges of the fish are as shown in the figure below. Point \( O \) represents the reference point on the sea surface.

见题面 Input 部分

见题面 Output 部分