LANDING

Points: 100

Time limit: 1.0s

Memory limit: 493M

Problem type

Sau khi khống chế thành công COVID 19, các đường bay đã được mở lại, nhu cầu đi lại tăng cao sau kì nghỉ Tê ́tdài nhất trong lịch sử. Hiện tại là thời điểm 0, có N máy bay đang tiếp cận để hạ cánh tại sân bay Cát Bi. Máy bay thứ i (1≤i≤N) có thể điều chỉnh tốc độ để hạ cánh ở một mốc thời điểm nguyên trong khoảng thời gian [Li,Ri]. Trong đó Li là thời điểm sớm nhất máy bay có thể hạ cánh, Ri là thời điểm muộn nhất máy bay phải hạ cánh, quá thời gian Ri, máy bay sẽ chuyển hướng hạ cánh tại sân bay khác. Khoảng thời gian Ri − Li được gọi là giới hạn chờ của máy bay thứ i và giới hạn này tất cả N máy bay là giống nhau.

Sân bay có K đường băng, có thể hoạt động độc lập và tiếp nhận các máy bay hạ cánh. Các máy bay phải thực hiện lệnh giãn cách X giây. Hay 2 máy bay liên tiếp hạ cánh trên một đường băng phải cách nhau ít nhất X giây.

Yêu cầu: Hãy lên phương án sắp xếp các máy bay, sao cho số lượng máy bay hạ cánh là nhiều nhất có thể. Nếu có cùng phương án đảm bảo số lượng máy bay hạ cánh nhiều nhất, tìm phương án tối ưu sao cho thời gian chênh lệch nhỏ nhất giữa 2 máy bay cùng hạ cánh trên một đường băng là lớn nhất.

Input:

Dòng đầu tiên ghi 3 số nguyên dương N, K, X (N≤10^5, K≤4, X≤10^9)
Tiếp theo là N dòng, mỗi dòng ghi 2 số Li, Ri (0≤Li≤Ri≤10^9)

Output:

gồm 2 số nguyên P và T được ghi trên một dòng, phân tách bởi dấu cách. Số thứ nhất P − là số máy bay lớn nhất có thể hạ cánh được;Số thứ hai T − là giá trị của chênh lệch nhỏ nhất giữa 2 máy bay bất kỳ trên cùng một đường băng trong phương án tối ưu tìm được. Nếu mỗi đường băng chỉ tiếp nhận không quá 1 máy bay thì ghi ra −1.

Sample Input

Sample Output

3 65

Subtask

1.  (16điểm) N≤8, K=1
2.  (12 điểm) N≤8, K=2
3.  (20 điểm) N≤16, K=1, 0≤ Li≤Ri≤100
4.  (16 điểm) N≤16, K=2, 0≤Li≤Ri≤100
5.   (20 điểm) N≤10^5, K=1
6.  (16 điểm) N≤10^5, 2≤K≤4

Comments

There are no comments at the moment.