Cảng biển

Sau nhiều năm cải tạo, cảng biển quốc tế Nam Hải vừa được mở cửa đón tàu trở lại. Hiện tại là thời điểm \(0\), có \(N\) tàu biển đang di chuyển để cập cảng. Tàu thứ \(i\) \((1 \le i \le N)\) có thể điều chỉnh tốc độ để cập cảng tại một mốc thời điểm nguyên nằm trong khoảng \([L_i, R_i]\). Trong đó \(L_i\) là thời điểm sớm nhất tàu có thể cập cảng, còn \(R_i\) là thời điểm muộn nhất bắt buộc phải cập cảng. Nếu sau thời điểm \(R_i\) tàu vẫn chưa được vào bến, nó sẽ buộc phải chuyển sang cảng khác.

Khoảng thời gian \(R_i - L_i\) được gọi là giới hạn chờ của tàu thứ \(i\), và tất cả các tàu đều có cùng giới hạn này.

Cảng Nam Hải có \(K\) bến đỗ, mỗi bến có thể hoạt động độc lập. Quy định an toàn hàng hải yêu cầu bất kỳ \(2\) tàu liên tiếp cập cùng một bến phải cách nhau ít nhất \(X\) giây.

Yêu cầu: Hãy xây dựng phương án sắp xếp để số lượng tàu cập cảng là nhiều nhất có thể. Nếu có nhiều phương án đạt cùng số lượng tàu tối đa, hãy chọn phương án mà trong đó khoảng cách nhỏ nhất giữa hai tàu bất kỳ cùng cập một bến là lớn nhất.

Input

• Dòng đầu tiên gồm \(3\) số nguyên dương \(N, K, X\) \((N \le 10^5, K \le 4, X \le 10^9)\).

• Tiếp theo \(N\) dòng, mỗi dòng ghi \(2\) số nguyên \(L_i, R_i\) \((0 \le L_i \le R_i \le 10^9)\).

Output

In ra hai số nguyên \(P\) và \(T\) trên cùng một dòng, cách nhau một dấu cách.

• \(P\) là số tàu nhiều nhất có thể cập cảng được.
• \(T\) là giá trị khoảng cách nhỏ nhất giữa hai tàu bất kỳ cùng cập một bến trong phương án tối ưu tìm được.
• Nếu trên mỗi bến không có quá \(1\) tàu cập cảng, in ra \(-1\).

Example

5 1 60
0 20
0 20
100 120
60 80
110 130

3 65

5 2 60
0 20
0 20
100 120
60 80
110 130

5 65

Scoring

• (16 điểm) \(N \leq 8\), \(K = 1\)
• (12 điểm) \(N \leq 8\), \(K = 2\)
• (20 điểm) \(N \leq 16\), \(K = 1\), \(0 \leq L_i \leq R_i \leq 100\)
• (16 điểm) \(N \leq 16\), \(K = 2\), \(0 \leq L_i \leq R_i \leq 100\)
• (20 điểm) \(N \leq 10^5\), \(K = 1\)
• (16 điểm) \(N \leq 10^5\), \(2 \leq K \leq 4\)