K. Kowtowing Our Leader
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The auditorium of the Institute of Mathematical Enlightenment, commonly known as IME, is the place where the greatest minds come together in order to provide exceptional lectures to the unwashed masses. Of course, the one who expels the greatest knowledge per word is our dear leader, the commander, who is one whose maximum happiness must be achieved.

So what happens is the following: over the course of the commander's exceptionally short one hundred year reign, he gives out $$$m$$$ lectures to his own dear students. At the end of each lecture, two students (not necessarily distinct) out of the $$$n$$$ watching the lecture are voluntarily chosen to ask a question at the end of the fabulous lecture and to thank him for the once-in-a-lifetime opportunity of being the recipients of such critical information.

We can say that the happiness of the commander is directly related to these two students who are chosen at the end; it is known for a fact that each student has a happiness value associated with them, and the commander's happiness is the values of the two students multiplied. As multiple lectures happen along his tenure, his total happiness ends up being the sum of his happiness after each one. However, it is also known that the commander really dislikes when the same ordered pair of students is chosen twice, so if a pair $$$(i, j)$$$ is chosen to respectively ask and thank, they can't be chosen in the same order again in a later lecture, but if the pair $$$(j, i)$$$ is chosen, then the commander won't notice the difference and as such won't dislike, unless, of course, $$$i$$$ and $$$j$$$ are the same person.

Under these circumstances, given all of this information in advance, you must figure out the maximum happiness of the commander at the end of his term.

This is a mere illustration of something.
Input

The first line contains two integers $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$ $$$(1 \leq m \leq n^2)$$$ — the amount of students watching the lectures and the amount of lectures.

The next line contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(1 \leq a_i \leq 10^{4})$$$ — the happiness value associated with each student.

Output

Output a single integer — the maximum happiness value that the commander can have after the $$$m$$$ lectures.

Example
Input
8 10
19 23 11 14 3 8 1 44
Output
8361
Note

Clearly, the $$$10$$$ best pairs to choose are:

$$$(a_8, a_8)$$$ –> $$$44 \times 44 = 1936$$$

$$$(a_8, a_2)$$$ –> $$$44 \times 23 = 1012$$$

$$$(a_2, a_8)$$$ –> $$$23 \times 44 = 1012$$$

$$$(a_8, a_1)$$$ –> $$$44 \times 19 = 836$$$

$$$(a_1, a_8)$$$ –> $$$19 \times 44 = 836$$$

$$$(a_8, a_4)$$$ –> $$$44 \times 14 = 616$$$

$$$(a_4, a_8)$$$ –> $$$14 \times 44 = 616$$$

$$$(a_2, a_2)$$$ –> $$$23 \times 23 = 529$$$

$$$(a_8, a_3)$$$ –> $$$44 \times 11 = 484$$$

$$$(a_3, a_8)$$$ –> $$$11 \times 44 = 484$$$

The sum of the products is $$$8361$$$.