Вася сильно устал от кредитов (из задачи F) и теперь хочет заработать деньги сам! Для этого он решил подготовить контест.
Васе предложено \(n\) задач. Они пронумерованы от \(1\) до \(n\). Сложность \(i\)-й задачи равна \(d_i\). Кроме того, задачи заданы в возрастающем относительно сложности порядке. Сложности всех задач различны. Для того чтобы добавить \(i\)-ю задачу в контест Васе нужно заплатить \(c_i\) бурлей автору. За каждую задачу в своем контесте Вася получит \(a\) бурлей.
Для того чтобы создать контест нужно выбрать непрерывный подотрезок задач.
Суммарный заработок за контест считается следующим образом:
Посчитайте максимальный Васин заработок, если он подготовит непрерывный подотрезок задач.
Первая строка содержит \(n\) и\(a\) (\(1 \le n \le 3 \cdot 10^5\), \(1 \le a \le 10^9\)) — количество предложенных задач и количество бурлей, которое Вася получает за одну задачу соответственно. В каждой из следующих \(n\) строк содержится два числа \(d_i\) и \(c_i\) (\(1 \le d_i, c_i \le 10^9, d_i < d_{i+1}\)).
Выведите одно число — максимальное количество бурлей, которое может заработать Вася.
5 10 1 15 5 3 6 11 7 2 11 22
13
3 5 1 8 2 19 3 11
0
3500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач