Highest Average Beauty Score

You are given a collection of (N) images, each with an associated integer beauty score. Your task is to select exactly (M) images such that the average beauty score is maximized. The average is computed using integer division (i.e., rounded down), according to the formula: (\text{Average} = \left\lfloor \frac{\sum_{i=1}^{M} s_i}{M} \right\rfloor). Design an efficient solution to solve this problem.

inputFormat

The input is provided via standard input (stdin) and consists of two lines. The first line contains two space-separated integers: (N) (the total number of images) and (M) (the number of images to be chosen). The second line contains (N) space-separated integers representing the beauty scores of each image.

outputFormat

Output a single integer to standard output (stdout) representing the highest possible average beauty score computed as described.## sample

5 3
4 8 2 6 1

6