Скоро Новый Год, и Макс решил сделать для всех своих друзей подарки — коробки с конфетами.
Сейчас перед Максом стоят N пустых коробок, пронумерованных от 1 до N. Макс добавляет в них конфеты следующим образом: на i-м шаге он кладёт Ki конфет в каждую коробку, имеющую номер от Li до Ri включительно.
Когда Макс разложил все конфеты, ему стало интересно, в какой из коробок находится больше всего конфет. Помогите ему найти эту коробку!
Выходные данные
Выведите одно целое число — номер коробки, содержащей максимальное количество конфет. Если подходящих ответов несколько, выведите максимальный.