Tưới cây (Watering Trees)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một khu vườn gồm $N$ luống cây nằm liên tiếp trên một hàng, được đánh số từ $1$ đến $N$.

Trong khu vườn có $M$ hệ thống tưới tự động. Khi hệ thống tưới thứ $i$ hoạt động, nó tưới đồng thời tất cả các luống cây có chỉ số từ $L_i$ đến $R_i$, kể cả hai đầu mút.

Sau khi cả $M$ hệ thống đều đã hoạt động đúng một lần, số lần một luống cây được tưới bằng số hệ thống có phạm vi tưới chứa luống đó.

Một luống cây được gọi là đủ nước nếu nó được tưới ít nhất $K$ lần.

Một đoạn đủ nước liên tiếp là một dãy các luống cây có chỉ số liên tiếp, trong đó mọi luống cây đều đủ nước.

Hãy xác định:

• tổng số luống cây đủ nước;
• số luống cây lớn nhất có thể nằm trong một đoạn đủ nước liên tiếp.

Nếu không có luống cây nào đủ nước thì cả hai kết quả đều bằng $0$.

Input

• Dòng đầu chứa ba số nguyên $N$, $M$, $K$.
• $M$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $L_i$, $R_i$, mô tả phạm vi tưới của hệ thống thứ $i$.

Các số nguyên trên cùng một dòng được phân cách bởi dấu cách.

Output

In ra một dòng gồm hai số nguyên $A$ và $B$, cách nhau bởi một dấu cách, trong đó:

• $A$ là tổng số luống cây đủ nước;
• $B$ là số luống cây lớn nhất trong một đoạn đủ nước liên tiếp.

Nếu không có luống cây nào đủ nước, in:

0 0

Subtask

• Subtask 1: $1 \le N \le 2000$; $1 \le M \le 2000$; $1 \le K \le M$; $1 \le L_i \le R_i \le N$ với $1 \le i \le M$.
• Subtask 2: $1 \le N \le 10^6$; $1 \le M \le 2\cdot10^5$; $K=1$; $1 \le L_i \le R_i \le N$ với $1 \le i \le M$.
• Subtask 3: $1 \le N \le 10^6$; $1 \le K \le M \le 2\cdot10^5$; $1 \le L_i \le R_i \le N$ với $1 \le i \le M$.

Ví dụ

Ví dụ 1

Input

10 4 2
1 5
3 7
6 10
4 4

Output

5 5

Giải thích

Số lần được tưới của các luống cây từ $1$ đến $10$ lần lượt là:

$$1,\ 1,\ 2,\ 3,\ 2,\ 2,\ 2,\ 1,\ 1,\ 1.$$

Vì $K=2$, các luống cây $3,4,5,6,7$ đều được tưới ít nhất hai lần nên có tổng cộng $5$ luống đủ nước.

Năm luống này nằm liên tiếp từ luống $3$ đến luống $7$, do đó đoạn đủ nước liên tiếp dài nhất có $5$ luống.

Ví dụ 2

Input

8 3 1
2 3
5 5
7 8

Output

5 2

Giải thích

Vì $K=1$, một luống cây đủ nước nếu được ít nhất một hệ thống tưới.

Các luống cây đủ nước là $2,3,5,7,8$, nên có tổng cộng $5$ luống đủ nước.

Các đoạn đủ nước liên tiếp là $[2,3]$, $[5,5]$ và $[7,8]$. Hai đoạn dài nhất là $[2,3]$ và $[7,8]$, mỗi đoạn gồm $2$ luống.

Ví dụ 3

Input

6 3 2
1 2
3 4
5 6

Output

0 0

Giải thích

Mỗi luống cây chỉ thuộc phạm vi tưới của đúng một hệ thống, trong khi một luống cần được tưới ít nhất $K=2$ lần mới được coi là đủ nước.

Vì không có luống cây nào đủ nước nên cả hai kết quả đều bằng $0$.