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

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Barber of the Army of Mages

Time limit: 0.5 second
Memory limit: 64 MB
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 (tipi < qiti + si − 1). If at least one magician disappears before being completely shaved, output a single word “No”.


3 2
1 3
1 3
1 3
1 2
1 3
2 3
2 1
1 3
1 3
Problem Author: Magaz Asanov
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1774. Barber of the Army of Mages