Optimal Ride Sharing

You are given m cars and p passengers. Each car can take up to n passengers. Every passenger has a route defined by a start point and an end point. The objective is to assign all passengers to the available cars (in the order determined by a permutation) such that the total distance traveled is minimized.

For a given car carrying a set of passengers, the distance traveled is defined by the difference between the maximum end point and the minimum start point of the passengers assigned to that car. In mathematical terms, if a car carries passengers indexed by a set S, then the distance for that car is given by:

[ D = \max_{i\in S} {e_i} - \min_{i\in S} {s_i} ]

Your task is to determine the distribution that yields the minimum total distance traveled over all cars and output the result along with the passenger assignments. The answer should be printed with the total distance formatted to one decimal place, followed by m lines, each describing the passengers assigned to a car. Note that the passenger indices are 1-indexed in the output.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains three integers m, n, and p, where:
• m is the number of cars,
• n is the maximum number of passengers each car can take,
• p is the total number of passengers.
• Each of the following p lines contains two integers: the start and end points of a passenger's route.

Example input:

3 2 6
1 5
2 6
3 8
4 7
5 9
6 10

outputFormat

The output should be written to stdout and formatted as follows:

• The first line contains the minimum total distance traveled (formatted with one decimal place).
• Each of the next m lines starts with the number of passengers assigned to that car, followed by the 1-indexed passenger IDs for that car separated by spaces.

Example output:

15.0
2 1 2
2 3 4
2 5 6

## sample

3 2 6
1 5
2 6
3 8
4 7
5 9
6 10

15.0
2 1 2
2 3 4
2 5 6

</p>