Пакетна обробка завдань#4144

Пакетна обробка завдань

0,1 секунди

256 мегабайтів

Дуже легка

Є послідовність з $N$ робіт, які потрібно обробити на одній машині. Роботи пронумеровані від $1$ до $N$ , тобто послідовність виглядає як $1, 2, \dots, N$ 1, 2, \ldots, N. Послідовність робіт потрібно розбити на одну або більше партій, причому кожна партія складається з послідовних робіт у цій послідовності.

Обробка починається у момент часу $0$ . Партії обробляються одна за одною, починаючи з першої. Якщо партія $b$ містить роботи з меншими номерами, ніж партія $c$ , то партія $b$ виконується раніше за партію $c$ . Роботи у кожній партії обробляються на машині послідовно. Одразу після того, як усі роботи у партії оброблено, машина видає результати всіх робіт цієї партії. Час виведення для роботи $j$ — це момент, коли партія, що містить $j$ , завершується.

Для кожної партії потрібен час на переналаштування машини $S$ . Для кожної роботи $i$ відомі коефіцієнт вартості $F_{i}$ F_i та час обробки $T_{i}$ T_i. Якщо партія містить роботи $x, x + 1, \dots, x + k$ x, x+1, \ldots, x+k й починається у момент часу $t$ , то час виведення для кожної роботи цієї партії дорівнює

t + S + (T_{x} + T_{x + 1} + \dots + T_{x + k})

t + S + (T_x + T_{x+1} + \ldots + T_{x+k})

Зверніть увагу, що результати всіх робіт у партії видаються машиною одночасно. Якщо час виведення для роботи $i$ — $O_{i}$ O_i, то її вартість складає $O_{i} \times F_{i}$ O_i \times F_i.

Наприклад, нехай маємо $5$ робіт, час налаштування $S = 1$ S = 1, $(T_{1}, T_{2}, T_{3}, T_{4}, T_{5}) = (1, 3, 4, 2, 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)$ (F_1, F_2, F_3, F_4, F_5) = (3, 2, 3, 3, 4).

Якщо розбити роботи на три партії: ${1, 2}, {3}, {4, 5}$ \{1, 2\}, \{3\}, \{4, 5\}, то часи виведення становлять $(O_{1}, O_{2}, O_{3}, O_{4}, O_{5}) = (5, 5, 10, 14, 14)$ (O_1, O_2, O_3, O_4, O_5) = (5, 5, 10, 14, 14), а вартості робіт — $(15, 10, 30, 42, 56)$ (15, 10, 30, 42, 56) відповідно. Загальна вартість для такого розбиття — $153$ .

Потрібно написати програму, яка для заданого часу переналаштування партії та послідовності робіт з відомими часами обробки і коефіцієнтами вартості знаходить мінімальну можливу загальну вартість.

Вхідні дані

Ваша програма читає зі стандартного введення.

Перший рядок містить число робіт $N$ , $1 \leq N \leq 10000$ 1 \leq N \leq 10000.
Другий рядок містить час налаштування партії $S$ ( $0 \leq S \leq 50$ 0 \leq S \leq 50).
Наступні $N$ рядків містять інформацію про роботи $1, 2, \dots, N$ 1, 2, \ldots, N у такому порядку. У кожному з цих рядків:
- Ціле число $T_{i}$ T_i ( $1 \leq T_{i} \leq 100$ 1 \leq T_i \leq 100) — час обробки $i$ -ї роботи.
- Ціле число $F_{i}$ F_i ( $1 \leq F_{i} \leq 100$ 1 \leq F_i \leq 100) — коефіцієнт вартості $i$ -ї роботи.

Вихідні дані

Ваша програма повинна вивести у стандартний вивід один рядок з єдиним цілим числом — мінімально можливою загальною вартістю.

Приклади

Приклад 1