Оптимізація Посадки на Рейс
Пітер — менеджер з посадки в аеропорту Байтленду. Його завдання — оптимізувати процес посадки пасажирів. Літаки в Байтленді мають 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 пасажирами.
Вихідні дані
Виведіть одне число — мінімально можливу складність посадки.