AT_abc461_c [ABC461C] Variety

There are $ N $ gems. The color (represented as an integer) of the $ i $ -th gem is $ C_i $ and its value is $ V_i $ . Choose $ K $ gems from these $ N $ gems. Here, the chosen gems must have at least $ M $ distinct colors. Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)

The input is given from Standard Input in the following format: > $ N $ $ K $ $ M $ > $ C_1 $ $ V_1 $ > $ C_2 $ $ V_2 $ > $ \vdots $ > $ C_N $ $ V_N $

Output the maximum possible total value of the chosen gems as an integer.

### Sample Explanation 1 In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors. Choosing gems $ 2, 3, 5 $ gives colors $ 1, 1, 3 $ , which are two distinct colors. Their total value is $ 40 + 50 + 20 = 110 $ , and this is the maximum possible value. ### Sample Explanation 2 The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors. Choosing gems $ 3, 4, 5 $ gives colors $ 1, 2, 3 $ , which are three distinct colors. Their total value is $ 50 + 10 + 20 = 80 $ , and this is the maximum possible value. ### Sample Explanation 3 Beware of overflow. ### Constraints - $ 1 \leq M \leq K \leq N \leq 2 \times 10^5 $ - $ 1 \leq C_i \leq N $ - $ 1 \leq V_i \leq 10^9 $ - There exist gems of at least $ M $ distinct colors. - All input values are integers.