Розклад#10677

Розклад

1 секунда

128 мегабайтів

Дуже складна

Не всі жарти вдаються, але всі рішення, надіслані сьогодні під час змагання, будуть перевірені після його завершення, а не під час, як зазвичай.

Припустимо, що ви надіслали $N$ рішень, кожне з яких має унікальний номер від $1$ до $N$ . Система обробляє ці рішення групами. Рішення з послідовними номерами можуть бути поділені на одну або кілька груп, і система перевіряє ці групи по черзі, починаючи з першої. Перевірка починається з часу $0$ . Спочатку система перевіряє всі рішення першої групи, і автори отримують результати цієї групи одночасно і миттєво. Якщо є наступна група, вона перевіряється далі, і результати для цієї групи також відкриваються. Так процес триває, поки всі рішення не будуть перевірені і результати не стануть відомі.

Кожне рішення $i$ перевіряється за $T_{i}$ T_i секунд, а ступінь занепокоєння автора щодо результату — $C_{i}$ C_i. Перед перевіркою кожної групи для налаштування системи потрібно $K$ секунд. Всі значення $T_{i}$ T_i, $C_{i}$ C_i та $K$ — цілі числа.

Наприклад, якщо рішення під номерами $i, i + 1, \dots, i + j$ i, i + 1, \ldots, i + j перевіряються як група, починаючи з моменту $Z$ , результати для цієї групи стануть відомі на $Z + K + (T_{i} + T_{i + 1} + \dots + T_{i + j})$ Z + K + (T_i + T_{i + 1} + \ldots + T_{i + j}) секунді. Важливо, що автори отримують результати одночасно і миттєво.

Якщо результат $i$ -го рішення стане відомий у $P_{i}$ P_i-ту секунду, ступінь занепокоєння автора зростає на $C_{i} \times P_{i}$ C_i \times P_i. Ваше завдання — мінімізувати загальний рівень занепокоєння всіх учасників.

Вхідні дані

Перший рядок містить $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100) — кількість тестів. Для кожного тесту подано два числа: $N$ ( $1 \leq N \leq 2 \times 1 0^{5}$ 1 \leq N \leq 2\times 10^{5}), ( $\sum N \leq 2 \times 1 0^{5}$ \sum N \leq 2\times 10^{5}) і $K$ ( $0 \leq K \leq 50$ 0 \leq K \leq 50) — кількість рішень і час, витрачений на конфігурацію системи. Далі йде $N$ рядків, кожен з яких містить два цілих числа $T_{i}$ T_i ( $1 \leq T_{i} \leq 100$ 1 \leq T_i \leq 100) і $C_{i}$ C_i ( $1 \leq C_{i} \leq 100$ 1 \leq C_i \leq 100) — час перевірки $i$ -го рішення та ступінь занепокоєння автора.

Вихідні дані

Для кожного тесту виведіть мінімально можливу суму занепокоєння. Кожну відповідь виводьте з нового рядка.

Приклади

Приклад 1

Примітка

Розглянемо приклад із $t = 1$ t=1 тестом. В цьому тесті $N = 5$ N=5 рішень і $K = 1$ K=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) і $(C_{1}, C_{2}, C_{3}, C_{4}, C_{5}) = (3, 2, 3, 3, 4)$ (C_1, C_2, C_3, C_4, C_5) = (3, 2, 3, 3, 4). Розділимо рішення на $3$ групи: ${1, 2}, {3}, {4, 5}$ \{1, 2\}, \{3\}, \{4, 5\}.

У такому випадку результати будуть відомі в моменти $(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}) = (5, 5, 10, 14, 14)$ (P_1, P_2, P_3, P_4, P_5) = (5, 5, 10, 14, 14). Ступінь занепокоєння кожного автора: $(15, 10, 30, 42, 56)$ (15, 10, 30, 42, 56). Загальна сума занепокоєння $15 + 10 + 30 + 42 + 56 = 153$ 15 + 10 + 30 + 42 + 56 = 153. У цьому прикладі не можна отримати меншу суму.

Оцінювання

Задача складається з наступних $8$ підзадач: