Ranking sums P21654


Statement
 

pdf   zip

thehtml

You are given n integer numbers. If you compute all the (

n
2

) sums of any two of those numbers, and you sort them all, which is the k-th of those sums?

For instance, if n = 3 and you are given the numbers 6, 6, and 4, you can make three sums: 6 + 6 = 12, 6 + 4 = 10, and 6 + 4 = 10. Therefore, the first of those sums is 10, the second is ‍10, and the third is 12.

Input

Input consists of several cases, each with k and n, followed by the n numbers, all between 1 ‍and 108. Assume 2 ≤ n ≤ 4 · 104 and 1 ≤ k ≤ (

n
2

).

Output

For every case, print the k-th sum of all the pairs of numbers.

Public test cases

  • Input

    1 3  6 6 4
2 3  6 6 4
3 3  6 6 4
1 2  1 100000000
1 4  10 10 10 10
6 4  10 10 10 10

    Output

    10
10
12
100000001
20
20
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++