Доброго времени суток!

Помогите решить такую задачу:

Есть M торговцев. Каждый торговец торгует начиная с города L_i до R_i. Свой товар торговец начинает торговать с города L_i за цену X_i, и с каждым городом цена товара увеличивается на 1 единицу, т.е В городе L_i за X_i , в городе L_i+1 за X_i+1, в городе R_i за X_i+ R_i — L_i+1.

И для каждого города нужно определить максимальную цену товара за всю историю.