pandacity

Problem Description

The population size and land area of Pandacity is growing and a more efficient transport system is needed to travel around the area. Pandacity is split up into N neighbourhoods conveniently labelled 1,2,...,N and the government would like to build bi-directional train tracks between these neighbourhoods.

They want to build the tracks such as all the neighbourhoods can be reached from each other by train. The cost of building a train track between two neighbourhoods is 1 dollar while the satisfaction gained by the citizens for building a train track is the sum of the number of inhabitants of the two neighbourhoods that the train track connects.

Furthermore, the government does not want to have two different ways of travelling between two neighbourhoods by train so as not to confuse the citizens. Given a budget of B dollars, where 1 ≤ B ≤ N*N the government would like to maximise the total satisfaction gained by building the train tracks according to the specifications above.

Subtasks

The number of inhabitants in each neighbourhoods will be positive and fit into a 32-bit signed integer.

Subtask 1(10%): 1 ≤ N ≤ 20

Subtask 2(20%): 1 ≤ N ≤ 1000

Subtask 3(70%): 1 ≤ N ≤ 1000000

Subtask 4(0%): Sample Testcase

Input

The first line of input will contain two integers, N and B

The next N lines of input will each contain one integer where the (i+1)th line indicates the number of inhabitants in neighbourhood i

Output

The output should only be a single integer, the maximum total satisfaction that can be gained by building train tracks within the given constraints. If there is no way to build the tracks satisfying all the above conditions, output -1

Sample Input

3 2
1
2
3

Sample output

9

Explanation

Build a train track between neighbourhoods 1 and 3 with satisfaction 4, and one between neighbourhoods 2 and 3 with satisfaction 5