Военная академия
(Время: 1 сек. Память: 16 Мб Сложность: 69%)
Военная академия Флатландии недавно получила запрос от правительства на подготовку n секретных агентов для важнейшей операции против их давнего дружеского соседа Попландии. Каждый агент получит специальную миссию, i-я миссия требует чтобы квалификация агента, который будет ее выполнять, была как минимум pi.
Главный инструктор академии выбрал n студентов академии и назначил каждому из них одну из миссий i-й из выбранных студентов будет выполнять миссию i. Теперь для подготовки агентов необходимо провести несколько тренировок.
С каждым студентом можно проводить личные тренировки, кроме того, можно проводить групповые тренировки со всеми студентами вместе. В начале квалификация каждого студента равна нулю. Каждый студент характеризуется своей обучаемостью qi и общительностью si. После личных тренировок в течение m часов квалификация студента вырастает на mqi. После групповых тренировок в течении m часов квалификация студента вырастает на msi. Тренировки могут продолжаться произвольное неотрицательное количество часов (не обязательно целое).
Тренировки проводятся инструкторами. За час личной тренировки инструктору требуется заплатить a рублей, а за час групповой тренировки b рублей.
Помогите руководству академии спланировать тренировки так, чтобы выполнить заказ правительства и минимизировать сумму, потраченную на оплату работы инструкторов.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа: n (1 ≤ n ≤ 100), a и b (1 ≤ a, b ≤ 106). Каждая из следующих n строк содержит по три целых числа: pi, qi и si (1 ≤ pi, qi, si ≤ 1000).
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать одно вещественное число: w – общую стоимость подготовки студентов к операции. Вторая строка должна содержать одно вещественное число g – продолжительность групповой тренировки. Третья строка должна содержать n вещественных чисел – продолжительности личных тренировок студентов. При проверке вашего решения будет использоваться сравнение вещественных чисел с точностью 10−6.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 50 13
10 10 2
3 5 1 | 59.0
3.0
0.4 0.0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
