Преподаватели ЛКШ очень любят поспать. Но, как назло, именно в этот вечер Мишаня подготовил музыкальный фреш, состоящий из $$$N$$$ композиций, по одной минуте каждая. Резкие перепады громкости не дают преподавателям уснуть и они попросили Мишу поддерживать одну и ту же громкость, пока они не погрузятся в объятия Морфея, то есть в течение $$$M$$$ минут. Однако понижение громкости песен вызывает недовольство школьников, что может повлиять на успех мероприятия.

У каждой музыкальной композиции есть свой максимальный уровень громкости $$$H_i$$$. Известно, что понижение громкости $$$i$$$-й композиции на единицу уменьшит успех мероприятия на $$$A_i$$$ единиц. Ваша задача — минимизировать кол-во успеха, которые Миша потеряет из-за сонных преподавателей.