CF711C Coloring Trees

ZS the Coder and Chris the Baboon has arrived at Udayland! They walked in the park where $ n $ trees grow. They decided to be naughty and color the trees in the park. The trees are numbered with integers from $ 1 $ to $ n $ from left to right. Initially, tree $ i $ has color $ c_{i} $ . ZS the Coder and Chris the Baboon recognizes only $ m $ different colors, so $ 0

The first line contains three integers, $ n $ , $ m $ and $ k $ ( $ 1

Print a single integer, the minimum amount of paint needed to color the trees. If there are no valid tree colorings of beauty $ k $ , print $ -1 $ .

In the first sample case, coloring the trees with colors $ 2,1,1 $ minimizes the amount of paint used, which equals to $ 2+3+5=10 $ . Note that $ 1,1,1 $ would not be valid because the beauty of such coloring equals to $ 1 $ ( $ {1,1,1} $ is a way to group the trees into a single group of the same color). In the second sample case, all the trees are colored, but the beauty of the coloring is $ 3 $ , so there is no valid coloring, and the answer is $ -1 $ . In the last sample case, all the trees are colored and the beauty of the coloring matches $ k $ , so no paint is used and the answer is $ 0 $ .