На Славянском Базаре проводится уличная гонка на электросамокатах.

Маршрут проходит по круговой трассе длины $m$ км, на которой расположены $n$ зарядок, в каждой из которых можно заправится на любое целое неотрицательное количество единиц электроэнергии, при этом покупка на $i$-й заправке $v$ единиц энергии обойдётся в $c_i \cdot v^2$ рублей. Одной единицы электроэнергии хватает на $1$ км. Зарядка с номером $i$ находится на расстоянии $p_i$ от начала трассы.

Вам требуется найти минимальную стоимость, за которую можно проехать всю трассу, если начать от какой-либо зарядки и заряжаться по пути.

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

В первой строке даны два целых числа $n$, $m$ ($1 \le n \le 400\,000$, $1 \le m \le 10^9$, $n \le m$) – количество зарядок и длина пути соответственно.

В следующих $n$ строках находится по 2 числа, которые описывают $i$-ю зарядку: $p_i$, $c_i$ ($0 \le p_i < m$, $1 \le c_i \le n$) – координата и коэффициент стоимости.

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

В первой строке выведите одно число – минимальную стоимость.

Подзадачи