Not all jokes are successful, but all solutions submitted during the competition today will be checked after the competition, and not during the competition as usual. Suppose that you have sent $N$ solutions and we will enumerate these solutions with integers from $1$ to $N$. So, the system has solutions with numbers $1,2,....,N$. The system checks solutions in groups. Решения с последовательными номерами могут разделиться на одну или несколько групп и система из этих групп начиная с первой по одному последовательно будет проверять. Процесс проверки начинается с $0$-го времени. Сначала система проверит все решения первой группы и авторы \textbf{одновременно,мгновенно} узнают результаты решений этой группы. Далее, если есть $2$-ая группа, то по тем же правилам решения проверяются и узнаются результаты второй группы. Так далее по этим же правилам проверяются все решения и авторы узнают результаты своих решений. Изначально мы знаем, что $i$-ое решение проверяется системой за $T_i$ секунд и степень ожидания результата у автора решения $C_i$ . В то же время, прежде чем проверить каждую группу нужно настроить систему и это делается за $K$ секунд. $T_i$, $C_i$ и $K$ являются целыми числами. Для примера, если решения с номерами $i, i + 1,....,i + j$ будут проверяться группой и если проверка этой группы начинается на $Z$ секунде, то в этой группе результат каждого решения будет известно на $Z + K + (T_i + T_{i + 1} + ..... + T_{i + j}$) секунде. Подчеркнем ,что результаты становятся известны авторам одновременно , мгновенно. Если результат $i$-го решения известно на $P_i$-ой секунде , то у автора данного решения степень беспокойства растет на $C_i * P_i$ . Тем меньше степень беспокойства участников , тем это означает уровень оптимательности данной системы . Вы на основе данных должны выяснить минимальную суммарную степень беспокойства всех участников соревнования. \subsection{\bfseries{Входные данные}} Первая строка содержит $t$ ($1 \leq t \leq 100$) – количество тестов. Для каждого теста даётся два числа $N$ ($1 \leq N \leq 2*10^{5}$), ($\sum N \leq 2*10^{5}$) и $K$ ($0 \leq K \leq 50$) – количество решений и затрачиваемое время на конфигурацию системы , еще позже дается $N$ строк , каждая строка содержит два целых числа $T_i$ ($1 \leq T_i \leq 100$) и $C_i$ ($1 \leq C_i \leq 100$) – сколько секунд тратится на проверку $i$-го решения и степень ожидания автора данного решения. \subsection{\bfseries{Выходные данные}} Выведите для каждого теста минимальную суммарную степень беспокойства. Ответ на каждый следующий тест , должен начинаться с новой строки . \subsection{\bfseries{Подзадачи}} Данная задача состоит из нижеследующих $8$ подзадач: \includegraphics{https://static.e-olymp.com/content/27/27cb5d4fe7bd55b76cfa1011529e34566ab5df9b.png} \subsection{\bfseries{Разбор примера}} В данном примере есть $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$.