Пакетна обробка завдань
Існує послідовність N завдань, призначених для виконання на одній машині. Завдання пронумеровані від 1 до N наступним чином 1, 2, …, N. Завдання повинні бути так згруповані в один чи декілька пакетів, щоб кожен пакет складався і ідучих один за одним завдань початкової послвдовноств. Виконання першого завдання починається у момент часу 0. Пакеты обробляються один за одним, починаючи з першого, наступним чином. Якщо пакет b містить завдання з меншими номерами, ніж пакет c, то пакет b потрапляє на обробку раніше пакету c. Завдання кожного пакету виконуються на машині послідовно. Відразу ж після того, як усі заадання пакету виконано, машина виводить результати виконання усіх завдань цього пакета. Час завершення виконання j-го завдання визначається часом завершення обробки всього пакету, що містить j-те завдання.
Щоб підготувати машину до обробки кожного пакету, необхідний час S, який назвемо підготовчим. Для кожного i-го завдання відомий вартісний коефіцієнт F_i та час T_i, необхідний для виконання цього завдання. Якщо пакет складається з завдань x, x+1, … , x+k і потрапляє на обробку у момент часу t, то час завершення виконання кожного завдання пакету розраховується за формулою
t + S + (Tx + Tx+1 + … + Tx+k).
Зауважимо, що машина виводить результати усіх завдань пакета в один і той же момент часу. Якщо час завершення виконання i-го завдання - O_i, то вартість виконання цього заідання складає O_i×F_i. Нехай є 5 завдань і відомо: S = 1; (T_1, T_2, T_3, T_4, T_5) = (1, 3, 4, 2, 1); (F_1, F_2, F_3, F_4, F_5) = (3, 2, 3, 3, 4).
Якщо завдання згруповані у три пакети {1, 2}, {3}, {4, 5}, то можна обчислити час завершення виконання для них (O_1, O_2, O_3, O_4, O_5) = (5, 5, 10, 14, 14) та вартості виконання завдань (15, 10, 30, 42, 56), відповідно. Загальна вартість виконання згрупованих у пакети завдань визначається як сума вартостей виконання кожного завдання. Таким чином, загальна вартість виконання усіх завдань для запропонованого прикладу буде становити 153.
Вам задано величину пвдготовчого часу S та послідовність N завдань, для кожного з яких визначено час виконання та вартісний коефіцієнт. Потрібно написати програму, яка обчисює мінімально можливу загальну вартість виконання послідовності N завдань.
Вхідні дані
Ваша програма повинна читати дані зі стандартного входу. Перший рядок містить кількість задань N (1 ≤ N ≤ 10000). Другий рядок містить підготовчий час S, який є цілим числом (0 ≤ S ≤ 50). Наступні N рядків містять інформацію про завдання 1, 2, …, N у вказаному порядку. В кожному з цих рядків першим задається ціле число T_i (1 ≤ T_i ≤ 100) - час виконання завдання. За ним слідує ціле число F_i (1 ≤ i ≤ 100) - вартістний коефіцієнт завдання.
Вихідні дані
Ваша програма повинна записувати у стандартний вихід один рядок, що місить одне ціле число - мінімальну загальну вартість виконання послідовності N завдань.