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
31-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