借阅登记

题目背景

学校图书馆的书架排成一长排，编号从左到右依次为 $1$ 到 $n$。今天图书馆开放了 $m$ 次“班级集体借阅”，每次借阅针对一段连续编号的书架，每个被覆盖到的书架都会被借走一本书。管理员想知道：哪个书架最受欢迎，以及有多少个书架被借走的书达到了某个数量。

题目描述

有 $n$ 个书架，编号 $1$ 到 $n$。今天共有 $m$ 条借阅记录，第 $i$ 条记录用两个整数 $l_i, r_i$ 描述，表示编号在 $[l_i, r_i]$ 内的每个书架都被借走了一本书。

所有借阅记录都发生完之后，请你回答两个问题：

1. 被借走书本数量最多的书架，被借走了多少本书；
2. 有多少个书架被借走的书本数量不少于 $k$ 本。

初始时每个书架被借走的数量都是 $0$。

输入格式

从标准输入读入数据。

第一行三个整数 $n, m, k$。

接下来 $m$ 行，每行两个整数 $l_i, r_i$，描述一条借阅记录，保证 $1 \le l_i \le r_i \le n$。

输出格式

输出到标准输出。

输出两行：第一行是被借走书本数量的最大值，第二行是被借走数量不少于 $k$ 的书架个数。

样例 1 输入

5 3 2
1 3
2 5
2 2

样例 1 输出

3
2

样例 1 解释

五个书架被借走的数量依次是 $1, 3, 2, 1, 1$。最大值是 $3$；被借走数量不少于 $2$ 本的书架是 $2$ 号和 $3$ 号，共 $2$ 个。

样例 2 输入

4 1 1
1 4

样例 2 输出

1
4

特殊性质

• 特殊性质 A：每条记录都只覆盖一个书架，即对所有 $i$ 都有 $l_i = r_i$。此时每个书架被借走的数量就是覆盖它的记录条数，可以用桶直接统计。
• 特殊性质 B：每条记录都从 $1$ 号书架开始，即对所有 $i$ 都有 $l_i = 1$。此时 $r_i$ 越小、覆盖的次数越多，只需要统计每个位置被"哪些记录的右端点覆盖"。

数据范围与子任务

部分分提示

• 子任务 1 直接对每条记录把区间内每个书架的数量加一，复杂度 $O(nm)$。
• 子任务 2 有特殊性质：满足 A 时用桶统计每个位置出现在多少条记录里；满足 B 时统计“有多少条记录的 $r_i \ge$ 当前位置”即可，可以用后缀和。
• 子任务 3 用差分：在 $l_i$ 处 $+1$、在 $r_i+1$ 处 $-1$，最后做一次前缀和就能得到每个书架的数量，复杂度 $O(n+m)$。

注意被借走的数量最多可能达到 $m$，且书架数量很多，请使用合适的数据类型并注意数组边界（$r_i = n$ 时要在 $n+1$ 处减一）。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。