Hide

Problem G
Almennir Borgarar

Languages en is
/problems/almennirborgarar/file/statement/en/img-0001.jpg
Image from Unsplash
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 \leq n \leq 2\cdot 10^5$), the number of grills, and $m$ ($0 \leq m \leq 10^9$), the number of contestants ahead of Benni in line.

Then there is a line with $n$ integers, $t_1, t_2, \ldots , t_ n$, where $t_ i$ ($1 \leq t_ i \leq 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 \leq 100$

2

20

$n, m \leq 10^3$

3

20

$m, t_ i \leq 10^3$

4

10

$m \leq 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

Please log in to submit a solution to this problem

Log in