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.
Warn: 本題有 specialjudge
There are multiple test case in the input file.
For each test case:
The first line contains two space-separated integers n and k, 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, 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”.
3 2 1 3 1 3 1 3 2 1 1 3 1 3
Yes 1 2 1 3 2 3 No
Migrated from old NTUJ.
Ural 1774
| No. | Testdata Range | Score |
|---|