Сервери
Комп'ютерна мережа в будинку була побудована так, що кожен новий комп'ютер підключався до останнього з уже підключених. Жодні два комп'ютери в мережі не мали додаткових зв'язків між собою. Таким чином, мережа складається з послідовно з'єднаних n комп'ютерів. Сусіди обмінювалися інформацією, але згодом зрозуміли, що їм потрібні проксі-сервери. Спільнота вирішила встановити проксі-сервери на рівно k комп'ютерах. Залишилося лише визначити, які комп'ютери обрати. Головним критерієм є мінімізація щомісячної вартості обслуговування всіх комп'ютерів.
Кожен комп'ютер має тариф обслуговування, виражений у рублях за метр дроту. Вартість обслуговування комп'ютера сервером дорівнює тарифу комп'ютера, помноженому на загальну довжину дроту від цього комп'ютера до сервера, який його обслуговує.
Ваше завдання — написати програму, яка вибере k комп'ютерів для встановлення проксі-серверів, щоб загальні витрати на обслуговування всіх комп'ютерів були мінімальними.
Вхідні дані
У першому рядку записано два цілі числа n і k — кількість комп'ютерів у мережі та кількість проксі-серверів, які потрібно встановити (1 ≤ k ≤ n ≤ 2000).
Усі комп'ютери в мережі пронумеровані від 1 до n у порядку підключення.
У другому рядку записано одне ціле число t_{1} — тариф обслуговування першого комп'ютера.
У наступних n - 1 рядках записано через пробіл по два цілі невід'ємні числа l_{i}, t_{i} — інформація про решту комп'ютерів у мережі за порядковими номерами. l_{i} — довжина дроту, що з'єднує i-й комп'ютер із сусіднім з меншим номером, t_{i} — тариф обслуговування цього комп'ютера (2 ≤ i ≤ n). Усі l_{i} і t_{i} не перевищують 10^6.
Вихідні дані
У першому рядку виведіть мінімальну вартість обслуговування всіх комп'ютерів усіма серверами. У другому рядку мають бути записані через пробіл k номерів комп'ютерів, на які потрібно встановити сервери. Якщо існує кілька варіантів розміщення, дозволяється вивести будь-який з них.