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”.
2 16 25
7 8 9 10
Problem Author: Alex Samsonov
Problem Source: NEERC 2011, Eastern subregional contest