Minimizing Machine Cleaning in an Ice Cream Shop

Your ice cream shop has n customers in line and m flavors available. However, the shop only has k ice cream machines. Each customer has a preferred flavor. When a customer comes, if the assigned machine already has the flavor they want, no cleaning is needed; otherwise, you must clean the machine and change its flavor. Note that if a machine is used for the first time, cleaning is required, and if a machine is never used, no cleaning cost is incurred. The customers arrive in order from 1 to n. As the owner, your task is to assign each customer to a machine so that the total number of cleaning operations is minimized. Formulate an optimal strategy and output the minimum number of cleaning operations required.

Hint: This problem is analogous to the optimal page replacement algorithm (Belady's algorithm) in caching.

inputFormat

The first line contains three integers n, m, and k -- the number of customers, the number of flavors, and the number of machines respectively. The second line contains n integers where the i-th integer denotes the flavor desired by the i-th customer.

outputFormat

Output a single integer: the minimum number of cleaning operations required.

sample

5 3 2
1 2 1 3 1

3