Сервери#2881
У певному будинку була створена комп’ютерна мережа шляхом підключення кожного нового комп’ютера до останнього вже підключеного. Після підключення жодні два комп’ютери не з’єднувалися між собою вдруге. У підсумку було підключено комп’ютерів послідовно. Сусіди обмінювалися інформацією між собою, але згодом зрозуміли, що їм потрібні проксі-сервери. Жителі вирішили встановити проксі-сервери рівно на комп’ютерах. Лишилося вибрати, на яких саме комп’ютерах їх встановити. Основна мета — мінімізувати щомісячні витрати на обслуговування всіх комп’ютерів із серверами.
Кожен комп’ютер має тариф обслуговування, виражений у євро за метр дроту. Вартість обслуговування комп’ютера сервером обчислюється як тариф цього комп’ютера, помножений на сумарну довжину дроту від цього комп’ютера до сервера, який його обслуговує.
Ваше завдання — написати програму, яка обирає комп’ютерів для встановлення проксі-серверів так, щоб мінімізувати загальні витрати на обслуговування всіх комп’ютерів.
У першому рядку задано два цілі числа і — кількість комп’ютерів у мережі та кількість проксі-серверів, які треба встановити (1 \leq k \leq n \leq 2000).
Усі комп’ютери у мережі пронумеровані від до за порядком підключення.
У другому рядку задано одне ціле число t_1 — тариф обслуговування першого комп’ютера.
У наступних n-1 рядках кожен рядок містить два невід’ємних цілих числа l_i та t_i — інформацію про інші комп’ютери мережі у порядку їх номерів. l_i — довжина дроту, яким -й комп’ютер з’єднано з сусідом із меншим номером, а t_i — тариф цього комп’ютера (2 \leq i \leq n). Усі l_i та t_i не перевищують 10^6.
У першому рядку виведіть мінімальні витрати на обслуговування всіх комп’ютерів усіма серверами. У другому рядку виведіть номерів комп’ютерів, на яких мають бути встановлені сервери, у будь-якому порядку через пропуск. Якщо існує кілька відповідних конфігурацій, дозволяється вивести будь-яку з них.
Приклад 1