When I slept soundly last night, a dream took me back to the times when I was taking my college entrance contest. I was given this problem:

Let $$$n$$$ be a positive integer and $$$S$$$ be a multiset of $$$\{1, 2, ..., n\}$$$. Integer $$$i\,(1 \leq i \leq n)$$$ appears $$$a_i \geq 0$$$ times in $$$S$$$. Also, I was given a positive integer $$$k$$$. A partition of $$$S$$$ into multisets, namely $$$\cup_{i=1}^t S_i$$$, is valid iff all of the following three conditions hold:

(1) $$$\cup_{i=1}^t S_i = S$$$.

(2) $$$\forall 1 \leq i < j \leq t,\,S_i \neq S_j$$$.

(3) $$$\forall 1 \leq i \leq t$$$, the size of $$$S_i$$$ is less or equal than $$$k$$$, i.e., $$$|S_i| \leq k$$$.

Find the minimum possible number of distinct multisets in the partition of $$$S$$$.

For example, if $$$k=2$$$ and $$$S=\{1, 1, 1, 2, 2, 2\}$$$, the answer is $$$1$$$ because you can decompose $$$S$$$ into $$$3$$$ $$$\{1, 2\}$$$, so you should answer $$$1$$$ because the problem asks for the distinct multisets.

When I wake up, I find this problem looks easy but I cannot solve it even if $$$k=2$$$. Is this problem greedy or related to the maximum flow? How about $$$k>2$$$?