tourist

Problem Description

An eccentric tourist has decided to visit some of the most beautiful Italian cities. In his luggage, together with an Italian/wherever-he-comes-from phrasebook, he has a number of large coins made with pure gold.

The tourist has already chosen a list of N cities to travel across, and intends to follow his plan until he runs out of money (so he might not reach the last cities in his list). He starts in the first city, and travels from one city to the next one, following the order he has established and paying one golden coin per route.

When he is in a city (included the first one), he can spend the night in a hotel in order to visit that city. However, he can only stay one night in each city at maximum. If he does so, he has to pay the hotel one golden coin, and his happiness increases by a value that depends on a city.

Clearly, the tourist is interested in maximising the happiness he gains by suitably using the coins during this holiday. Given an array containing each of the amount of happiness that can be gained by visiting each city, calculate the maximum amount of happiness he can gain with K golden coins.

Input

The first line of input will contain two integers, N and K.
The second line of input will contain N integers, with the ith integer representing the amount of happiness gained if the tourist visits city i.

Output

Your output should contain one integer, the maximum amount of happiness that can be gained using K golden coins.

Limits

For all testcases, K and happiness value will range from 0 to 2³¹-1.
Subtask 1 (18%): N ≤ 10.
Subtask 2 (1%): N = 42.
Subtask 3 (22%): N ≤ 200.
Subtask 4 (26%): N ≤ 1 000.
Subtask 5 (33%): N ≤ 1 000 000.
Subtask 6 (0%): As per sample testcases.

Sample Input 1

4 5
4 5 2 7

Sample Output 1

12