Simplified Maximum Diversity Problem
The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take one item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.