题目描述

售票处在出售音乐会门票，但它不销售单个座位的门票，而是销售固定数量的连续座位的成组门票。该售票处办公室已收到大量采购订单。一组座位的采购订单指定该组座位中最低的座位号。而办公室可能无法完成所有采购订单。此外，如果它只完全按照采购订单中的要求分配座位，那么大量作位可能会保持空置。因此，办公室采用以下分配和定价策略。如果采购订单被接受并且分配的座位正是所要求的座位，那么购买者支付全价（$2$ petaks）。如果采购订单被接受，但分配的座位与请求的座位不同（至少在一个位置上），则购买者支付半价（$1$ petak）。目标是使总收入最大化。
请您编写一个程序来计算可以实现的最大收入，并将座位分配给选定的订单以实现该收入。

输入格式

第一行包含两个整数，$M$ 和 $L$。$M$ 是座位数，$L$ 是每组中连续的座位号。座位号从 $1$ 到 $M$。第二行包含一个整数 $N$，即采购订单的数量。第三行包含 $N$ 个整数，定义采购订单，其行中的第 $i$ 个数字 $z$ 表示第 $i$ 个购买者要求从座位 $z$ 开始到座位 $z+L-1$ 结束的一组座位。

输出格式

第一行包含一个整数 $S$，即最大收入。第二行包含一个整数 $Q$，即已接受订单的数量。 接下来的 $Q$ 行描述了座位分配。每行包含一对整数 $x$ $y$。一对 $x$ $y$ 表示购买者 $x$ 从座位号 $y$ 开始获得座位。这些行必须按座位号的升序排列。

20 3
7
4 2 10 9 16 15 17

9
6
4 1
1 4
2 7
3 10
6 13
5 16

提示

数据规模与约定

对于 $100 \%$ 的数据， $1 \leq M \leq 3×10^4$，$1 \leq L \leq 100$，$1 \leq N \leq 10^5$，$1 \leq z \leq M-L+1$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Ticket Office。
由