#K65202. Maximal Score Calculation

    ID: 32145 Type: Default 1000ms 256MiB

Maximal Score Calculation

Maximal Score Calculation

You are given a target with m circles. Each circle is characterized by its radius and an associated score. You also have k arrows at your disposal. Each arrow can hit exactly one circle. The objective is to maximize your total score by choosing k circles such that the sum of their scores is as high as possible.

Formally, you are given an integer \(m\) representing the number of circles, followed by \(m\) pairs of integers \((r, p)\), where \(r\) is the radius (which is not used in the calculation) and \(p\) is the score of that circle. You are also given an integer \(k\) indicating the number of arrows. Your task is to compute the maximum achievable total score by selecting the \(k\) circles with the highest scores.

The total score is defined as:

[ \text{Total Score} = \sum_{i=1}^{k} p_{i} \quad \text{(where } p_i \text{ are the top } k \text{ scores)} ]

Note that the radius is provided for each circle but does not influence the result.

inputFormat

The input is read from standard input (stdin) and has the following format:

  1. The first line contains two space-separated integers: \(m\) (the number of circles) and \(k\) (the number of arrows).
  2. The next \(m\) lines each contain two space-separated integers \(r\) and \(p\), representing the radius and score of a circle.

Constraints:

  • 1 \(\leq m \leq 10^5\)
  • 1 \(\leq k \leq m\)

outputFormat

Print a single integer to standard output (stdout), which is the maximum total score that can be achieved by selecting the \(k\) circles with the highest scores.

## sample
3 2
10 5
20 10
30 15
25