5. JOI 2013 - Fish
Phía tây lục địa Úc là Ấn Độ Dương rộng lớn. Nhà nghiên cứu hải dương JOI đang nghiên cứu đặc tính của \(N\) loài cá sống tại đây.
Mỗi loài cá có một vùng sinh sống xác định trong biển, có dạng hình hộp chữ nhật. Cá có thể di chuyển đến mọi điểm trong vùng sinh sống của mình, kể cả biên, nhưng không bao giờ đi ra ngoài vùng đó. Một điểm trong biển được biểu diễn bởi ba số thực \((x,y,d)\): khi nhìn từ trên cao, điểm này nằm cách một vị trí mốc \(x\) đơn vị về phía đông và \(y\) đơn vị về phía bắc, đồng thời có độ sâu \(d\) tính từ mặt biển. Giả sử mặt biển là một mặt phẳng.
JOI muốn biết phần biển nơi vùng sinh sống của ít nhất \(K\) loài cá chồng lên nhau lớn đến mức nào. Hãy viết chương trình tính tổng thể tích của toàn bộ phần biển đó.
Yêu cầu
Tính tổng thể tích phần biển nằm trong vùng sinh sống của ít nhất \(K\) loài cá.
Dữ liệu vào
Dữ liệu vào gồm \(1+N\) dòng.
- Dòng đầu tiên chứa hai số nguyên \(N,K\) (\(1\le K\le N\le50\)), cách nhau bởi dấu cách. Có \(N\) loài cá và cần tính thể tích phần biển nơi vùng sinh sống của ít nhất \(K\) loài chồng lên nhau.
- Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa sáu số nguyên \(X_{i,1},Y_{i,1},D_{i,1},X_{i,2},Y_{i,2},D_{i,2}\). Vùng sinh sống của loài cá thứ \(i\) là hình hộp chữ nhật có tám đỉnh sau:
Các tọa độ thỏa mãn:
- \(0\le X_{i,1}<X_{i,2}\le1000000=10^6\).
- \(0\le Y_{i,1}<Y_{i,2}\le1000000=10^6\).
- \(0\le D_{i,1}<D_{i,2}\le1000000=10^6\).
Dữ liệu ra
In ra một dòng chứa tổng thể tích của phần biển nơi vùng sinh sống của ít nhất \(K\) loài cá chồng lên nhau.
Ví dụ 1
Input
3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70Output
49000Chẳng hạn, điểm \((45,65,65)\) nằm trong vùng sinh sống của loài cá thứ \(1\) và thứ \(3\), nên thỏa mãn điều kiện. Ngược lại, điểm \((25,35,45)\) chỉ nằm trong vùng sinh sống của loài thứ \(2\), nên không thỏa mãn điều kiện.
Ví dụ 2
Input
1 1
0 0 0 1000000 1000000 1000000Output
1000000000000000000