Розклад

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

Спочатку ми знаємо, що $i$-те рішення перевіряється системою за $T_i$ секунд, і ступінь очікування результату у автора рішення $C_i$. Водночас, перед перевіркою кожної групи потрібно налаштувати систему, що займає $K$ секунд. $T_i$, $C_i$ і $K$ є цілими числами.

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

Якщо результат $i$-го рішення відомий на $P_i$-ій секунді, то ступінь занепокоєння автора цього рішення зростає на $C_i\times P_i$. Чим менша сумарна ступінь занепокоєння учасників, тим оптимальніша система.

Вам потрібно визначити мінімальну сумарну ступінь занепокоєння всіх учасників змагання на основі наданих даних.

Вхідні дані

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

Вихідні дані

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

Підзадачі

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

Розбір прикладу

У даному прикладі є $t=1$ тест. У цьому тесті кількість рішень $N=5$, і витрачається $K=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)$. Розглянемо випадок розділення рішень на $3$ групи, зазначене нижче: $1,2,3,4,5$

У цьому випадку результати дізнаються на $(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=153$. У цьому прикладі неможливо отримати сумарну ступінь занепокоєння менше ніж $153$.

Приклади