eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Flight Boarding Optimization

Flight Boarding Optimization

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Петр является исполнительным посадочным менеджером в аэропорту Байтляндии. Его задача - оптимизация посадочного процесса. Самолеты в Байтляндии имеют s рядов, пронумерованных с 1 до s. Каждый ряд имеет шесть мест, пронумерованных от A до F.

prb6265

There are n passengers, they form a queue and board the plane one by one. If the i-th passenger sits in a row r[i]then the difficulty of boarding for him is equal to the number of passengers boarded before him and sit in rows 1...r[i] - 1. The total difficulty of the boarding is the sum of difficulties for all passengers. For example, if there are ten passengers, and their seats are 6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A, in the queue order, then the difficulties of their boarding are 0, 0, 0, 2, 0, 2, 0, 7, 7, 5, and the total difficulty is 23.

To optimize the boarding, Peter wants to divide the plane into k zones. Every zone must be a continuous range of rows. Than the boarding process is performed in k phases. On every phase, one zone is selected and passengers whose seats are in this zone are boarding in the order they were in the initial queue. In the example above, if we divide the plane into two zones: rows 5 - 10 and rows 1 - 4, then during the first phase the passengers will take seats 6A, 5F, 10E, 8B, 5A, and during the second phase the passengers will take seats 4B, 2E, 2A, 3F, 1C, in this order. The total difficulty of the boarding will be 6.

Help Peter to find the division of the plane into k zones which minimizes the total difficulty of the boarding, given a specific queue of passengers.

Входные данные

The first line contains three integers n (1n1000), s (1s1000) and k (1k50, ks).

The next line contains n integers r[i] (1r[i]s).

Each row is occupied by at most 6 passengers.

Выходные данные

Output one number, the minimal possible difficulty of the boarding.

Пример

Входные данные #1
10 12 2
6 4 2 5 2 3 1 11 8 5
Выходные данные #1
6
Источник 2013 ACM NEERC, Northern Subregional Contest, St Petersburg, October 26