403197: GYM101064 D Black Hills golden jewels

In Rapid City are located the main producers of the Black Hills gold jewelry, a very popular product among tourists. The main characteristics of these jewels are the designs of leaves and grape clusters that are made with gold alloys in yellow, green and pink tones.

Planning a trip to Rapid City in 2017, Nay Suames decides that he wants to buy these famous jewels, but he doesn't have much money to spend. Searching for the lowest prices, he found a jewelry store that will have a sale in May, the same month he will travel to that city. Lucky guy!

The jewelry store intends to sell the jewels that were produced with small defects, in general, only perceivable by experts. The jewels are separated in N categories of defects. Even if the defect is imperceptible, the jewelry store can't sell the jewel at full price, so it gives a discount proportional to the defect.

Knowing the high demand for these jewels, the jewelry store created a system aiming to be fair and, at the same time, to prevent everybody from buying only the cheapest jewels. The clients have to make a queue and will be served one at a time. When their time comes, the client must choose two jewels from different categories. Furthermore, they can't choose the same combination of categories that was previously chosen by another client.

Nay asks for your help to find the minimum amount of money he needs, being the K-th client in the queue, so that it is guaranteed that he can buy two different jewels.

The first line contains two integers, N and K, , representing the number of categories and the position of Nay in the queue, respectively. The next line contains N integers a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁹), corresponding to the prices of each category.

Print a single integer, the minimum amount of money to guarantee that Nay can buy the jewels.

4 3
2 4 5 2

6

6 9
1 2 3 4 5 6

7