Amusement Park

Time limit1sMemory limit512 MB

Summary

Schedule N people through M machines, each with fixed play times, so that everyone plays every machine exactly once and the last finish time is minimized; output the time and each person's order and start times.

Level: Medium7 of 10
Topics: Greedy, Sorting, Simulation, Implementation
Solved: No attempts yet

Problem

An amusement park was recently built in the city of π, and it contains a pavilion of arcade machines. Each machine can be used by only one person at a time. The participants of the All-Russian Olympiad are planning to visit this pavilion.

The organizers face a difficult task: draw up a schedule of play on the machines for the olympiad participants so that each of the N participants can play on every machine, and the bus that takes the participants away from the olympiad park can leave for their place of residence as early as possible.

The time participants spend moving between machines, and between the bus and the pavilion, is zero. At any moment, each participant can either play on a machine or wait their turn, for example by walking around the park. For each of the M machines (M ≤ N), the play time ti on it is known (1 ≤ i ≤ M). Once started, play on a machine cannot be interrupted. The bus brings all olympiad participants to the park simultaneously at time zero.

Write a program that, given N, M, and ti, determines an optimal schedule of play on the machines for each participant.

Input

The first line of the input file contains two numbers: N and M (1 ≤ M ≤ N ≤ 100). The second line contains M integers ti (1 ≤ ti ≤ 100), each giving the play time on the i-th machine (1 ≤ i ≤ M). The numbers in the line are separated by single spaces.

Output

The first line must contain a single number: the earliest possible departure time of the bus from the amusement park. Then output N schedules of play on the machines, one for each participant. Each schedule is described in (M + 1) lines, the first of which is empty, followed by M lines describing the machines in the order this participant visits them. A visit to a machine is described by two integers: the machine number j (1 ≤ j ≤ M) and the time the participant starts playing on that machine.

Constraints

The numbers ti lie between 1 and 100, and N > M.

Examples2

Example 1
Input
```
2 1
2
```
Expected output
```
4

1 0

1 2
```
Example 2
Input
```
3 2
2 1
```
Expected output
```
6

1 0
2 2

1 2
2 4

2 0
1 4
```