Maximizing Concert Ticket Revenue

A concert ticket office sells tickets not as individual seats but in groups of \(L\) consecutive seats. The office has received M ticket purchase orders. Each order specifies the lowest seat number of the desired group (so the requested block is from \(r\) to \(r+L-1\)). Due to various constraints, it might not be possible to satisfy every order exactly.

In order to avoid having many unused seats, the office adopts the following allocation and pricing strategy:

• If an order is accepted and the allocated seats exactly match the requested block, the buyer pays full price \(2\) petaks.
• If an order is accepted but the allocated block differs from the requested block in at least one position, the buyer pays half price \(1\) petak.

The office must decide which orders to accept and how to assign a block of \(L\) consecutive, non‐overlapping seats to each accepted order in order to maximize total revenue.

You are given the total number of seats \(S\) (numbered from 1 to \(S\)), a fixed group size \(L\), and \(M\) orders. Each order provides a requested starting seat \(r\) and it is guaranteed that \(r+L-1 \le S\). You may assign any block of \(L\) consecutive seats (the block starting at any integer from 1 to \(S-L+1\)), with the restriction that blocks assigned to different orders must not overlap. Note that an order accepted with exactly its requested block yields a revenue of \(2\) petaks while any accepted order assigned a different block yields a revenue of \(1\) petak. Also, you cannot accept more than \(M\) orders.

Write a program to compute the maximum revenue achievable and also provide an allocation of seats to a selected subset of orders achieving that revenue. For the allocation, output the list of accepted orders (indexed in input order, starting from 1) along with the starting seat number of the block allocated to that order.

inputFormat

The first line contains three space‐separated integers: \(S\) (the total number of seats), \(L\) (the fixed number of consecutive seats per ticket group), and \(M\) (the number of orders).

Each of the following \(M\) lines contains a single integer \(r\), the requested starting seat number for that order. It is guaranteed that \(r + L - 1 \le S\).

outputFormat

On the first line, output the maximum total revenue that can be achieved.

On the second line, output an integer \(k\) representing the number of accepted orders (\(k \le M\)).

Then output \(k\) lines. Each line should contain two space‐separated integers: the order's index (1-indexed in the order given in input) and the starting seat number of the allocated block for that order.

sample

10 3 3
1
2
8

4
2
1 1
3 8