Zxr960115 содержит большое хозяйство. Он кормит m милых кошечек и держит у себя p кормильщиков. Через ферму проходит прямая дорога, а вдоль дороги расположено n холмов, пронумерованных от 1 до n, слева направо. Расстояние от холма i до i - 1 равняется di метров. Кормильщики живут на холме 1.
Однажды кошечкам захотелось порезвиться и они разбежались. Кошка i пошла к холму hi, дошла до него в момент времени ti, а затем стала ждать кормильщика на холме hi. Кормильщики должны собрать всех разбежавшихся кошек. Каждый кормильщик идет прямо от холма номер 1 до холма номер n, не останавливаясь у какого-либо холма, и собирает всех кошек, ожидающих на каждом холме. Кормильщики двигаются со скоростью 1 в единицу времени и достаточно сильны, чтобы собрать сколько угодно кошек.
Например, пусть имеется два холма (d2 = 1) и одна кошечка, которая дошла до холма 2 (h1 = 2) в момент времени 3. Тогда, если кормильщик отправится за кошками от холма 1 в момент времени 2 или 3, то он сможет забрать эту кошку. Но если он отправится от холма 1 в момент времени 1, то он не сможет этого сделать. Если кормильщик отправится за кошкой в момент времени 2, то кошка будет ждать его 0 единиц времени, если же он отправится в момент времени 3, то кошка будет ждать его 1 единицу времени.
Ваша задача — составить расписание отправки от холма 1 для кормильщиков так, чтобы общее время ожидания кошек до того как их заберут было минимальным.
Выходные данные
Выведите целое число, минимальную сумму времен ожидания всех кошек.
Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.