Sau khi khống chế thành công COVID ~19~, các đường bay đã được mở lại, nhu cầu đi lại tăng cao sau kì nghỉ Tết dài nhất trong lịch sử. Hiện tại là thời điểm ~0~, có ~N~ máy bay đang tiếp cận để hạ cánh tại sân bay Cát Bi. Máy bay thứ ~i~ ~(1 \leq i \leq N)~ có thể điều chỉnh tốc độ để hạ cánh ở một mốc thời điểm nguyên trong khoảng thời gian ~[L_i, R_i]~. Trong đó ~L_i~ là thời điểm sớm nhất máy bay có thể hạ cánh, ~R_i~ là thời điểm muộn nhất máy bay phải hạ cánh, quá thời gian ~R_i~, máy bay sẽ chuyển hướng hạ cánh tại sân bay khác. Khoảng thời gian ~R_i~ − ~L_i~ được gọi là giới hạn chờ của máy bay thứ ~i~ và giới hạn này tất cả ~N~ máy bay là giống nhau.

Sân bay có ~K~ đường băng, có thể hoạt động độc lập và tiếp nhận các máy bay hạ cánh. Các máy bay phải thực hiện lệnh giãn cách ~X~ giây. Hay ~2~ máy bay liên tiếp hạ cánh trên một đường băng phải cách nhau ít nhất ~X~ giây.

Yêu cầu: Hãy lên phương án sắp xếp các máy bay, sao cho số lượng máy bay hạ cánh là nhiều nhất có thể. Nếu có cùng phương án đảm bảo số lượng máy bay hạ cánh nhiều nhất, tìm phương án tối ưu sao cho thời gian chênh lệch nhỏ nhất giữa ~2~ máy bay cùng hạ cánh trên một đường băng là lớn nhất.

Input

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

Tiếp theo là ~N~ dòng, mỗi dòng ghi 2 số ~L_i, R_i~ ~(0 \le Li \le Ri \le 10^9)~

Output

Ghi ra: gồm ~2~ số nguyên ~T~ và ~P~ được ghi trên một dòng, phân tách bởi dấu cách. Số thứ nhất ~P~ − là số máy bay lớn nhất có thể hạ cánh được. Số thứ hai ~T~ − là giá trị của chênh lệch nhỏ nhất giữa ~2~ máy bay bất kỳ trên cùng một đường băng trong phương án tối ưu tìm được. Nếu mỗi đường băng chỉ tiếp nhận không quá ~1~ máy bay thì ghi ra ~-1~.

Giới hạn

Output luôn phải gồm ~2~ số nguyên. Nếu bạn in đúng số thứ nhất và sai số thứ hai, bạn được ~50\%~ số điểm của test. Nếu bạn in đúng cả hai số, bạn được ~100\%~ số điểm của test.

Subtask

1. ~(16~ điểm~)~ ~N \leq 8~, ~K = 1~
2. ~(12~ điểm~)~ ~N \leq 8~, ~K = 2~
3. ~(20~ điểm~)~ ~N \leq 16~, ~K = 1~, ~0 \leq L_i \leq R_i \leq 100~
4. ~(16~ điểm~)~ ~N \leq 16~, ~K = 2~, ~0 \leq L_i \leq R_i \leq 100~
5. ~(20~ điểm~)~ ~N \leq 10^{5}~, ~K = 1~
6. ~(16~ điểm~)~ ~N \leq 10^{5}~, ~2 \leq K \leq 4~

Sample Input 1

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

Sample Output 1

3 65

Sample Input 2

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

Sample Output 2

5 65

Sample Input 3

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

Sample Output 3

5 120

Note

Ở test ví dụ 1:

• Đường băng 1
  • MB ~1~ thời điểm ~0~
  • MB ~4~ thời điểm ~65~
  • MB ~5~ thời điểm ~130~ Ở test ví dụ 2:
• Đường băng 1
  • MB ~1~ thời điểm ~0~
  • MB ~4~ thời điểm ~65~
  • MB ~5~ thời điểm ~130~
• Đường băng 2
  • MB ~2~ thời điểm ~0~
  • MB ~3~ thời điểm ~100~ Ở test ví dụ 3:
• Đường băng 1
  • MB ~1~ thời điểm ~0~
  • MB ~3~ thời điểm ~120~
• Đường băng 2
  • MB ~4~ thời điểm ~60~
• Đường băng 3
  • MB ~2~ thời điểm ~0~
  • MB ~5~ thời điểm ~120~