Оптимизация посадки на рейс
Питер — менеджер по посадке в аэропорту Байтленда. Его задача — оптимизировать процесс посадки. Самолеты в Байтленде имеют s рядов, пронумерованных от 1 до s. В каждом ряду шесть мест, обозначенных от A до F.
В очереди на посадку стоят n пассажиров, которые садятся в самолет по одному. Если i-й пассажир садится в ряд r[i], то сложность его посадки равна количеству пассажиров, которые сели до него и заняли места в рядах от 1 до r[i] - 1. Общая сложность посадки — это сумма сложностей всех пассажиров. Например, если десять пассажиров занимают места 6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A в порядке очереди, то их сложности посадки будут 0, 0, 0, 2, 0, 2, 0, 7, 7, 5, а общая сложность составит 23.
Чтобы оптимизировать посадку, Питер хочет разделить самолет на k зон. Каждая зона должна быть непрерывным диапазоном рядов. Затем посадка будет проходить в k фаз. На каждой фазе выбирается одна зона, и пассажиры, чьи места находятся в этой зоне, садятся в порядке, в котором они стояли в начальной очереди. В приведенном выше примере, если разделить самолет на две зоны: ряды 5 – 10 и ряды 1 – 4, то в первую фазу пассажиры займут места 6A, 5F, 10E, 8B, 5A, а во вторую фазу — места 4B, 2E, 2A, 3F, 1C в этом порядке. Общая сложность посадки будет 6.
Помогите Питеру найти такое разделение самолета на k зон, которое минимизирует общую сложность посадки, учитывая заданную очередь пассажиров.
Входные данные
Первая строка содержит три целых числа n (1 ≤ n ≤ 1000), s (1 ≤ s ≤ 1000) и k (1 ≤ k ≤ 50, k ≤ s).
Следующая строка содержит n целых чисел r[i] (1 ≤ r[i] ≤ s).
Каждый ряд может быть занят не более чем 6 пассажирами.
Выходные данные
Выведите одно число — минимально возможную сложность посадки.