A. Abadi Pikosom
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

People are ready for vacation. One thing people like to do during vacation is going to amusement parks.

Kantipa is an operator of an amusement park ride. There are $$$N$$$ people queueing to ride the ride. These people are numbered from $$$1$$$ to $$$N$$$ in order from front to back. Each person has a value $$$A_i$$$.

Kantipa can ignore the popular convention of a queue and make these people ride the ride in any order that she allows. The ordering can be any of the $$$N!$$$ possible orderings. For an ordering of who rides the ride first which Kantipa decides on, the anger level of person $$$i$$$ is calculated as follows:

  1. Let $$$p$$$ signify that person $$$i$$$ is the $$$p$$$-th person who rides the ride.
  2. Let $$$s$$$ be the sum of the values of $$$A_j$$$ for every person $$$j$$$ that is further back than person $$$i$$$ in the queue but rides the ride earlier than person $$$i$$$.
  3. The anger level of person $$$i$$$ is $$$p\times A_i + s$$$.

For an ordering of who rides the ride first, the total anger level is the sum of anger levels of the entire $$$N$$$ people.

There are $$$N!$$$ possible orderings. Kantipa wants to construct an array of size $$$N!$$$ consisting of all of the total anger levels for every single ordering. Kantipa has an integer $$$K$$$, she wants to sort that array in non-decreasing order and get the $$$K$$$-th element. However, doing so manually takes a very long time. Can you help her find the desired value?

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 200\,000$$$; $$$1\leq K\leq\min(N!,200\,000)$$$) — the number of people in the queue and the index of the element asked in the sorted array.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 200\,000$$$) — the value of each person.

Output

A single integer representing the $$$K$$$-th element in the non-decreasing order of the array of the $$$N!$$$ total anger levels.

Examples
Input
3 4
2 6 5
Output
35
Input
4 7
1 1 1 1
Output
12
Note

In the first example, consider the $$$6$$$ orderings of who rides the ride first:

  • Person $$$1$$$, person $$$2$$$, person $$$3$$$. The total anger level is $$$2+12+15=29$$$.
  • Person $$$1$$$, person $$$3$$$, person $$$2$$$. The total anger level is $$$2+23+10=35$$$.
  • Person $$$2$$$, person $$$1$$$, person $$$3$$$. The total anger level is $$$10+6+15=31$$$.
  • Person $$$2$$$, person $$$3$$$, person $$$1$$$. The total anger level is $$$17+6+10=33$$$.
  • Person $$$3$$$, person $$$1$$$, person $$$2$$$. The total anger level is $$$9+23+5=37$$$.
  • Person $$$3$$$, person $$$2$$$, person $$$1$$$. The total anger level is $$$17+17+5=39$$$.

The sorted array is $$$[29, 31, 33, 35, 37, 39]$$$.