일반 버거

이미지 출처: Unsplash

여러 해 동안 Forritunarkeppni Framhaldsskólanna의 대회 참가자들은 점심으로 Hamborgarabúlla Tómasar의 맛있는 햄버거를 받아 왔다. 참가자들은 버거를 기다리는 동안 하나의 긴 줄을 서고, 그사이 Búllan의 요리사들은 버거를 준비하기 위해 열심히 일한다. Búllan의 요리사들은 매우 능숙하여 버거를 준비하는 데 시간이 전혀 걸리지 않는다. 유일한 예외는 버거가 그릴에서 익기를 기다려야 한다는 점이다. Búllan에는 $n$개의 작은 그릴이 있으며(번호는 $1$부터 $n$까지이다), 각 그릴에서는 한 번에 버거 하나만 구울 수 있다. 또한 그릴마다 온도가 달라 버거를 굽는 데 걸리는 시간도 서로 다르다. 요리사들이 이 시간을 측정한 결과, $i$번 그릴에서 버거 하나를 굽는 데 $t_i$초가 걸린다는 사실을 알아냈다.

이제 Benni는 버거를 받으려고 줄에서 들뜬 마음으로 기다리고 있지만, 그의 앞에는 $m$명의 참가자가 서 있다. 요리사들이 그릴을 최적으로 사용한다면 Benni가 자신의 버거를 받기까지 얼마나 걸리는가?

점수

그룹 | 점수 | 제한

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 | 추가 제한 없음

입력의 첫 번째 줄에는 그릴의 수를 나타내는 정수 $n$ ($1 \leq n \leq 2\cdot10^5$)와 Benni보다 앞에 줄 서 있는 참가자의 수를 나타내는 정수 $m$ ($0 \leq m \leq 10^9$)가 주어진다.

그다음 줄에는 $n$개의 정수 $t_1, t_2, \ldots, t_n$가 주어진다. 여기서 $t_i$ ($1 \leq t_i \leq 10^9$)는 $i$번 그릴에서 버거 하나를 굽는 데 걸리는 시간이다.

요리사들이 그릴을 최적으로 사용할 때, Benni가 자신의 버거를 받기 전까지 기다려야 하는 시간을 초 단위로 출력한다.