Задача №115272. Автомобильный туризм
Маша и Миша решили отправиться в автомобильный поход. Они планируют ехать вдоль длинной прямой дороги, на которой расположены \(n\) заправок. Пронумеруем заправки вдоль дороги от \(1\) до \(n\). Исходно машина расположена в городе, который находится в начале дороги, здесь же расположена первая заправка с номером \(1\).
Заправка с номером \(i\) располагается на расстоянии \(x_i\) от начала дороги. На этой заправке можно покупать бензин по цене \(p_i\) рублей за литр. На каждой заправке разрешается покупать только целое число литров бензина. Одного литра бензина хватает, чтобы проехать на расстояние \(1\) вдоль дороги. Вместимость бензобака машины составляет \(C\) литров, исходно он пуст.
У Миши и Маши есть бюджет в \(B\) рублей на покупку бензина. Как далеко вдоль дороги они смогут уехать, если об обратном пути они решили пока не думать?
Первая строка содержит три целых числа \(n\), \(B\) и \(C\) — количество заправок, бюджет в рублях и вместимость бензобака в литрах, соответственно (\(1 \le n \le 10^5\), \(1 \le B \le 10^9\), \(1 \le C \le 10^9\)).
Каждая из следующих \(n\) строк содержит по два целых числа \(x_i\) и \(p_i\) — координату \(i\)-й заправки и стоимость литра бензина на ней, соответственно (\(0 = x_1 < x_2 < \ldots < x_n \le 10^9\), \(1 \le p_i \le 10^9\)).
Выведите одно целое число — максимальное расстояние, на которое можно уехать.
В тесте из примера можно купить \(1\) литр бензина на первой заправке, проехать на расстояние \(1\), доехать до второй заправки, купить там \(5\) литров бензина, затем проехать на расстояние \(3\), доехав до третьей заправки. В этот момент в баке останется \(2\) литра бензина, после чего, купив еще \(1\) литр бензина, можно будет проехать расстояние \(3\), оказавшись на расстоянии \(7\) от начала дороги.
3 10 5 0 3 1 1 4 2
7