Petr, elected as a warlord of the army of mages, faced a challenging problem.
All magicians recruited in the army had heavy beards, which were quite
unacceptable for soldiers. Therefore, Petr ordered all recruits to shave their
beards as soon as possible. Of course, all magicians refused to do it, referring
to the fact they don't know any shaving spell. Fortunately, a magician Barberian
agreed to shave all recruits.
Barberian can cast a “Fusion Power” spell which shaves beards of at most k
magicians in one minute. In order to achieve full effect every magician should
be shaved twice: the first spell shaves close, the second spell shaves even closer.
For each recruit Petr appointed a time when he should visit Barberian.
Unfortunately, the discipline in the new army is still far from perfect, so
every magician will come to Barberian in time, but everyone will wait for the shave
until his patience is exhausted and will disappear after that.
Determine whether Barberian will be able to shave beards of all magicians
before they disappear.
The first line contains two space-separated integers n and k
(1 ≤ n, k ≤ 100), which are the number of recruits
in the army and the number of magicians Barber can shave simultaneously.
The i-th of the following n lines contains space-separated
integers ti and si
(0 ≤ ti ≤ 1000;
2 ≤ si ≤ 1000), which are
the time in minutes, at which the i-th magician must come to Barberian,
and the time in minutes he is ready to spend there, including shaving time.
If Barberian is able to shave beards of all magicians,
output “Yes” in the first line. The i-th of the following n
lines should contain a pair of integers pi,
qi, which are the moments at which Barberian should cast
the spell on the i-th magician (ti ≤ pi <
qi ≤ ti + si − 1).
If at least one magician disappears before being completely shaved,
output a single word “No”.
Problem Author: Magaz Asanov
Problem Source: XV Open USU Championship