Не все шутки бывают успешными, но все решения отправленные сегодня во время соревнование проверятся после соревнования, а не во время соревнования как бывает обычно. Предположим, что вы отправили N решений и эти решения пронумеруем целыми числами от 1 до N . Так, в системе есть решения с 1,2,....,N номерами. Система проверяет решения группами. Решения с последовательными номерами могут разделиться на одну или несколько групп и система из этих групп начиная с первой по одному последовательно будет проверять. Процесс проверки начинается с 0-го времени. Сначала система проверит все решения первой группы и авторы одновременно,мгновенно узнают результаты решений этой группы. Далее, если есть 2-ая группа, то по тем же правилам решения проверяются и узнаются результаты второй группы. Так далее по этим же правилам проверяются все решения и авторы узнают результаты своих решений.
Изначально мы знаем, что i-ое решение проверяется системой за Ti секунд и степень ожидания результата у автора решения Ci . В то же время, прежде чем проверить каждую группу нужно настроить систему и это делается за K секунд. Ti, Ci и K являются целыми числами.
Для примера, если решения с номерами i,i+1,....,i+j будут проверяться группой и если проверка этой группы начинается на Z секунде, то в этой группе результат каждого решения будет известно на Z+K+(Ti+Ti+1+.....+Ti+j) секунде. Подчеркнем ,что результаты становятся известны авторам одновременно , мгновенно.
Если результат i-го решения известно на Pi-ой секунде , то у автора данного решения степень беспокойства растет на Ci∗Pi . Тем меньше степень беспокойства участников , тем это означает уровень оптимательности данной системы .
Вы на основе данных должны выяснить минимальную суммарную степень беспокойства всех участников соревнования.
Первая строка содержит t (1≤t≤100) – количество тестов. Для каждого теста даётся два числа N (1≤N≤2∗105), (∑N≤2∗105) и K (0≤K≤50) – количество решений и затрачиваемое время на конфигурацию системы , еще позже дается N строк , каждая строка содержит два целых числа Ti (1≤Ti≤100) и Ci (1≤Ci≤100) – сколько секунд тратится на проверку i-го решения и степень ожидания автора данного решения.
Выведите для каждого теста минимальную суммарную степень беспокойства. Ответ на каждый следующий тест , должен начинаться с новой строки .
Данная задача состоит из нижеследующих 8 подзадач:
В данном примере есть t=1 тест. В данном тесте количество решений N=5, и тратится K=1 секунд на конфигурацию системы, и дано что (T1,T2,T3,T4,T5) = (1,3,4,2,1) и (C1,C2,C3,C4,C5) = (3,2,3,3,4). Посмотрим на случай разделения решений на 3 группы указанное ниже : 1,2,3,4,5
В данном случае результаты узнаются на (P1,P2,P3,P4,P5) = (5,5,10,14,14) секундах и степень беспокойства каждого автора решения становится (15,10,30,42,56) . Здесь, суммарная степень беспокойства это 15+10+30+42+56=153. В данном примере не возможно получить суммарную степень беспокойства меньше чем 153.