Description

The ticket office sells concert tickets, but it does not sell tickets for single seats. Instead, it sells group tickets for a fixed number of consecutive seats. The office has received a large number of purchase orders. A purchase order for a group of seats specifies the smallest seat number in that group. The office may not be able to fulfill all purchase orders. Also, if it assigns seats strictly according to the purchase orders, many seats may remain empty. Therefore, the office uses the following allocation and pricing strategy. If a purchase order is accepted and the assigned seats are exactly the requested seats, then the buyer pays full price ($2$ petaks). If a purchase order is accepted but the assigned seats differ from the requested seats (in at least one position), then the buyer pays half price ($1$ petak). The goal is to maximize the total revenue.
Please write a program to compute the maximum revenue that can be achieved, and assign seats to the selected orders to achieve this revenue.

Input Format

The first line contains two integers, $M$ and $L$. $M$ is the number of seats, and $L$ is the number of consecutive seats in each group. Seat numbers range from $1$ to $M$. The second line contains an integer $N$, the number of purchase orders. The third line contains $N$ integers defining the purchase orders. The $i$-th number $z$ in this line means that the $i$-th buyer requests a group of seats starting from seat $z$ and ending at seat $z+L-1$.

Output Format

The first line contains an integer $S$, the maximum revenue. The second line contains an integer $Q$, the number of accepted orders. The next $Q$ lines describe the seat assignments. Each line contains a pair of integers $x$ $y$. The pair $x$ $y$ means that buyer $x$ receives seats starting from seat number $y$. These lines must be sorted in increasing order of seat number.

20 3
7
4 2 10 9 16 15 17

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

Hint

Constraints

For $100\%$ of the testdata, $1 \leq M \leq 3 \times 10^4$, $1 \leq L \leq 100$, $1 \leq N \leq 10^5$, $1 \leq z \leq M-L+1$.

Notes

From Ticket Office, CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005.
Translated and整理 (zhengli) by

Translated by ChatGPT 5