Problem B
Almennir Borgarar

For years contestants in Forritunarkeppni Framhaldsskólanna have gotten delicious hamburgers from Hamborgarabúlla Tómasar for lunch. The contestants form an orderly line where they wait while the chefs are hard at work at the grills. Búllan’s chefs are very talented. They are so talented that they assemble the burger instantly. The only thing that takes time is the grilling process. Búllan has $n$ small grills (numbered from $1$ to $n$) and each grill can grill one burger at a time. The grills also work at different temperatures, so they don’t take the same time to grill a burger. The chefs have measured that grill $i$ takes $t_i$ seconds to grill a single burger.

Benni, an ardent competitive programmer (and hamburger enthusiast), is waiting in line with $m$ other contestants in front of him. How long will Benni have to wait if the chefs utilize the grills optimally?

Input

The first line of the input contains two integers $n$ ($1\le n\le 2\cdot {10}^5$), the number of grills, and $m$ ($0\le m\le {10}^9$), the number of contestants ahead of Benni in line.

Then there is a line with $n$ integers, $t_1,t_2,\dots ,t_n$, where $t_i$ ($1\le t_i\le {10}^9$) is the number of seconds it takes the $i$-th grill to grill a burger.

Output

Print the number of seconds Benni has to wait before he gets his burger, assuming the chefs utilize the grills optimally.

Scoring

Group	Points	Constraints
1	20	$n,m,t_i\le 100$
2	20	$n,m\le {10}^3$
3	20	$m,t_i\le {10}^3$
4	10	$m\le {10}^5$
5	30	No further constraints

Sample Input 1	Sample Output 1
2 6 1 2	5

Sample Input 2	Sample Output 2
3 10 2 7 5	14

Sample Input 3	Sample Output 3
4 6 10 120 25 30	50