P2072 Religious Problem

In a region there are many religions. Believers of different faiths often have conflicts. As the person responsible for public security, you need to separate them to prevent escalation.

It is known that there are $M$ religions (numbered $1\sim M$) and $N$ believers (numbered $1\sim N$), and each believer believes in exactly one religion. Now you need to split these $N$ believers, in order, into several groups. The danger value of a group is defined as the number of distinct religions in that group, and a group may not contain more than $K$ religions; otherwise it is infinitely dangerous. Problem: 1. Into how many groups at least must these $N$ believers be divided? 2. What is the minimum possible sum of the danger values of these groups?

The first line contains three positive integers $N,M,K$, separated by spaces. The second line contains $N$ positive integers, the religion number of each believer.

The first line contains one positive integer, the minimum number of groups. The second line contains one positive integer, the minimum total danger value.

Sample explanation: One optimal partition is: $$[1,2,3]\ \ /\ \ [4,3,4,3,2]\ \ /\ \ [1,2]$$ Constraints: For $20\%$ of the testdata, $N \le 20$. For $50\%$ of the testdata, $N \le 100$. For $100\%$ of the testdata, $1 \le N \le 1000$, $1 \le K < M \le 20$. Translated by ChatGPT 5