Иван учится в Берляндском Государственном Университете (БГУ). В берляндской неделе n дней, в каждый из них у Ивана могут быть занятия в университете.
В одном дне m рабочих часов, каждое занятие в университете длится ровно час. Если в какой-то день первое занятие у Ивана в течение i-го часа, а последнее — в течение j-го, то он тратит ровно j - i + 1 час в университете в этот день. Если в какой-либо день нет занятий, то Иван остается дома и проводит 0 часов в университете, соответственно.
Иван не любит много времени проводить в университете, поэтому он решил пропустить некоторые занятия. Он не может пропустить больше, чем k занятий за неделю. Сначала Иван решает, какие занятия он посетит, а какие пропустит. Дальше в каждый день приходит в университет перед первым занятием, которое он решил не пропускать, и уходит после последнего, которое он собрался посетить. Если Иван решил пропускать все занятия в какой-то день, то он не идет в университет вообще.
По заданным n, m, k и расписанию Ивана определите, какое минимальное количество часов он может провести в университете за неделю, если он не может пропустить больше k занятий.
Выходные данные
Выведите минимальное количество часов, которые Ивану придется провести в университете, если он не может пропустить больше k занятий.
Примечание
В первом примере Иван может пропустить любое из двух занятий в первый день, поэтому он потратит 1 час в первый день и 4 часа во второй.
Во втором примере Иван не может пропустить ни одного занятия, поэтому он потратит 4 часа в оба дня.