Путешественник планирует водный поход по реке. Он отметил пригодные для ночлега места и выписал расстояния до них от своего старта. Каждое из таких мест дополнительно характеризуется своей живописностью, так для i-го места для стоянки расстояние от старта равно x_i, а живописность равна b_i. Путешественник будет двигаться по реке в одном направлении, можно считать, что он стартует из точки 0 на координатной прямой, а места ночлега — это точки с координатами x_i.

Каждый день путешественник хочет проходить расстояние l. На практике же оказывается, что это не всегда возможно, ведь заканчивать путь каждый день ему необходимо в одном из мест для ночлега. Кроме того, в путешественнике борются два желания: каждый день проходить расстояние l и посетить наиболее живописные места.

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

Помогите спланировать путь таким образом, чтобы минимизировать относительное суммарное недовольство: суммарное недовольство поделенное на суммарную живописность всех использованных мест ночлега.

Маршрут путешественника обязательно должен заканчиваться в самом дальнем месте ночлега.