물고기의 서식 범위

문제

오스트레일리아 대륙의 서쪽에는 넓은 인도양이 펼쳐져 있다. 해양 연구자인 JOI 씨는 인도양에 서식하는 어떤 N 종류의 물고기의 성질에 대해 연구하고 있다.

각각의 물고기 종류에 대해, 바닷속에 직육면체 모양의 서식 범위가 정해져 있다. 물고기는 경계를 포함하여 서식 범위 안의 어느 장소로도 이동할 수 있지만, 서식 범위 밖으로 나가는 일은 결코 없다. 바닷속의 점은 3 개의 실수 (x, y, d) 로 표현된다: (x, y, d) 는 상공에서 보았을 때 어떤 지점을 기준으로 동쪽으로 x, 북쪽으로 y 만큼 나아간 위치이며, 해수면으로부터의 깊이가 d 인 점을 나타낸다. 단, 해수면은 평면이라고 하자.

JOI 씨는 K 종류 이상의 물고기의 서식 범위가 겹치는 장소가 얼마나 있는지 알고 싶다. 그러한 장소 전체의 부피를 구하는 프로그램을 작성하시오.

입력

입력은 1 + N 개의 줄로 이루어진다.

첫째 줄에는 2 개의 정수 N, K (1 ≦ K ≦ N ≦ 50) 이 공백으로 구분되어 주어진다. 이는 물고기가 N 종류이며, K 종류 이상의 물고기의 서식 범위가 겹치는 장소의 부피를 구하고 싶음을 나타낸다.

이어지는 N 개의 줄 중 i 번째 줄 (1 ≦ i ≦ N) 에는 6 개의 정수 $X_{i,1}$, $Y_{i,1}$, $D_{i,1}$, $X_{i,2}$, $Y_{i,2}$, $D_{i,2}$ (0 ≦ $X_{i,1}$ ＜ $X_{i,2}$ ≦ 1000000 (= $10^{6}$),0 ≦ $Y_{i,1}$ ＜ $Y_{i,2}$ ≦ 1000000 (= $10^{6}$),0 ≦ $D_{i,1}$ ＜ $D_{i,2}$ ≦ 1000000 (= $10^{6}$)) 이 주어진다. 이는 i 번째 종류의 물고기의 서식 범위가 8 개의 점 ($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}$) 을 꼭짓점으로 하는 직육면체임을 나타낸다.

출력

K 종류 이상의 물고기의 서식 범위가 겹치는 장소 전체의 부피를 한 줄로 출력한다.

예제 입력 1

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

예제 출력 1

49000

예제 1 에서, 예를 들어 점 (45, 65, 65) 는 1 번째 종류의 물고기와 3 번째 종류의 물고기의 서식 범위이므로 조건을 만족하는 장소이다. 한편, 점 (25, 35, 45) 는 2 번째 종류의 물고기만의 서식 범위이므로 조건을 만족하는 장소가 아니다. 또한, 물고기의 서식 범위는 아래 그림과 같다. 점 O 는 해수면 위의 기준 지점을 나타낸다.

예제 입력 2

1 1
0 0 0 1000000 1000000 1000000

예제 출력 2

1000000000000000000