Задача Bank2021. Для прискорення обслуговування клієнтів у банку встановлено K кас. Упродовж дня банк обслуговує N клієнтів. Для кожного з клієнтів відомо, в який час він приходить і скільки часу займає його обслуговування. Коли клієнт приходить до банку, він отримує талончик із зазначенням номера каси, до якої йому слід підійти. Шлях від входу до каси номер 1 займає 1 секунду, до каси 2 – 2 секунди тощо. Стільки ж займає зворотний шлях від каси до виходу. Якщо каса, до якої підійшов клієнт, зайнята, він чекає своєї черги біля каси, і його обслуговування починається, як тільки каса звільниться. Напишіть програму, яка призначить касу кожному клієнту так, щоб він вийшов із банку якомога раніше. Якщо клієнта існує кілька варіантів вибору кас, слід призначити йому касу з найменшим номером.
Технічні умови. Програма Bank2021 читає з пристрою стандартного введення у першому рядку два натуральні числа N <=1000,і K<=10000 – кількість клієнтів і кас, відповідно. У наступних N рядках задаються пари натуральних чисел Si та Ti (S,T<=10000)– момент приходу та час обслуговування клієнта. Дані задані у порядку зростання часу приходу клієнтів; жодні два клієнти не приходять одночасно. Програма виводить на пристрій стандартного виведення N чисел через пропуск, де кожне з чисел задає номер каси, де повинен обслуговуватися клієнт. Виводити номери кас слід у порядку, в якому клієнти приходять до банку.
Приклад:
|
Введення |
Виведення |
|
3 2 1 10 3 6 4 1 |
1 2 1 |