ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2011, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Steaks on Board

Time limit: 1.0 second
Memory limit: 64 MB
The Oceanic Airlines company has announced that starting from the new year all passengers of transoceanic flights will be able to taste the famous Ural steaks during the flight. Unlike the standard meals, the steaks will be fresh, hot, and incredibly delicious because they will be cooked right on board.
Each passenger can specify at check-in the exact time when she wants her steak to be served. A steak is cooked by frying each of its sides on a frying pan continuously for one minute. If a steak is cooked too early, it won't be delicious enough, so the cooking must start no earlier than x minutes before the steak is served.
Unfortunately, each Oceanic Airlines plane is equipped with only one electric stove and one frying pan. No more than k steaks can be cooked on the frying pan simultaneously. The stove can be switched off when nothing is cooked. The chef wants to serve the orders of all the passengers on time while minimizing the time during which the stove is switched on. Help the chef.


The first line contains the integers x and k (2 ≤ x ≤ 1 000; 1 ≤ k ≤ 50). In the second line you are given the number n of ordered steaks (1 ≤ n ≤ 50). In the third line there are integers t1, …, tn, which define the times when the steaks should be served (2 ≤ ti ≤ 1 000). The times are given in nondecreasing order and are counted from the moment of departure.


If the chef can cook the ordered steaks on time, output in the first line the minimum number of minutes during which the electric stove will be working. In the ith of the following n lines output two nonnegative integers, which are the times when the ith steak should be put on the frying pan on one side and on the other side, respectively. The steaks must be described in the same order in which they are given in the input. If there are several possible answers, output any of them. If it is impossible to serve all the orders on time, output “-1”.


10 2
2 16 25
0 1
11 15
15 17
10 2
7 8 9 10
3 6
4 5
3 6
4 5
2 1
2 2
Problem Author: Alex Samsonov
Problem Source: NEERC 2011, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1895. Steaks on Board