eolymp
bolt
Try our new interface for solving problems
Problems

Amusement Park

Amusement Park

Time limit 1 second
Memory limit 256 MiB

An amusement park was recently built in the city . The park has a hall of slot machines. Each machine is designed for one person. The All-Russia Olympiad program is planned to visit this hall.

The organizers faced a difficult task - to schedule the games on machines for participants of Olympiad so that each of the N participants was able to play on each machine, and the bus, taking away the members of the Olympic Park, could go to a place of residence as early as possible.

Travel time between the participants machines, as well as between the bus and the pavilion is considered to be zero. Each of the participants at any one time can both play on the machine and wait their turn, for example, walking through the park. For each of the M (MN) is known a game machine it t_i (1iM). Break started the game on the machine impossible. The bus brings all the participants in the Olympic Park both at time zero.

Required to write a program that, given the numbers N, M and t_i determines an optimal schedule games on slot machines for each of the participants.

Input data

The first line of the input file contains two numbers: N and M (1MN100). In the second row of M are given integers t_i (1t_i100), each of which sets the game on the i^th machine (1iM). The numbers in the row are separated by single spaces.

Output data

The first line should display a single number - the minimum possible time bus departure from the amusement park. Next, you need to bring games to N scheduling slots, one for each participant. Each table is described in the (M+1) rows, the first of which - is empty, and is followed by M lines describing the machines in order of their visit to this party. Visit the automaton is described by two integers: the number of machine j (1jM) and the time the game participant on this machine.

Examples

Input example #1
1 1
1
Output example #1
1

1 0
Source XXIII National Olympiad in Informatics, Perm, Second Round, 04/15/2011