Не все шутки бывают успешными, но все решения отправленные сегодня во время соревнование проверятся после соревнования, а не во время соревнования как бывает обычно. Предположим, что вы отправили $N$ решений и эти решения пронумеруем целыми числами от $1$ до $N$ . Так, в системе есть решения с $1,2,....,N$ номерами. Система проверяет решения группами. Решения с последовательными номерами могут разделиться на одну или несколько групп и система из этих групп начиная с первой по одному последовательно будет проверять. Процесс проверки начинается с $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$.