D. Жара
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Между официальной столицей Берляндии и ее культурной столицей есть единственная дорога, пролегающая через n областей. В каждой области свой уникальный климат, поэтому летом в i-ой (1 ≤ i ≤ n) области стоит устойчивая температура ti градусов.

Этим летом группа из m школьников хочет добраться из официальной столицы в культурную для посещения музеев и достопримечательностей. Для перевоза школьников между городами организаторы экскурсии используют автобусы, но в них иногда бывает очень жарко, точнее, если при проезде i-ой области в некотором автобусе находятся k школьников, то температура внутри автобуса равна ti + k градусов.

Разумеется, мало кому нравится, когда в автобусе жарко, и поэтому, если при проезде i-ой области температура в некотором автобусе больше, чем Ti градусов, то каждый из школьников в этом автобусе требует неустойку за некомфортные условия в размере xi рублей, причем, неустойка взымается в каждой области, где температура в автобусе превышает установленный предел.

Для экономии денег организаторы поездки могут в начале поездки и между областями произвольным образом менять количество автобусов (конечно же, для проезда любой области требуется хотя бы один автобус), на которых едут дети, а также произвольным образом пересаживать их между автобусами, однако, каждый из автобусов на i-ом участке обойдется организаторам в costi рублей. Обратите внимание, что плата за пересадку не взимается.

Ваша задача — найти минимальное количество рублей, которое придется потратить организаторам, чтобы перевезти всех школьников.

Входные данные

В первой строке входных данных записаны два целых числа n и m (1 ≤ n ≤ 105; 1 ≤ m ≤ 106) — количество областей на пути и количество школьников в группе соответственно. Далее в n строках записаны по четыре целых числа: в i-ой из них записаны ti, Ti, xi и costi (1 ≤ ti, Ti, xi, costi ≤ 106). Числа в строках разделены единичными пробелами.

Выходные данные

Выведите единственное целое число — минимальное количество рублей, которое придется потратить организаторам, чтобы перевезти всех школьников.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
2 10
30 35 1 100
20 35 10 10
Выходные данные
120
Входные данные
3 100
10 30 1000 1
5 10 1000 3
10 40 1000 100000
Выходные данные
200065
Примечание

В первом примере при проезде первой области организаторы будут использовать один автобус, однако температура внутри него станет равна 30 + 10 = 40 градусов, и каждый из 10 школьников потребует неустойку. При проезде второй области так же будет использован только один автобус, но температура внутри будет меньше критической. Итого организаторы потратят 100 + 10 + 10 = 120 рублей.