시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 3 3 (100%) 3
문제
크로아티안 대표단은, M명의 사람으로 이루어져있고, 호주에서 주최하는 IOI 2013에 가게되었다. 그들은 현재 공항의 체크인 줄에 서서 기다리고 있다. 그곳에는 N개의 체크인 데스크가 열려있었다. 몇몇의 공무원은 다른사람보다 더 효율적으로 일했고, 그래서 데스크들의 운영속도는 다르게 되었다. k번째 데스크에서, 한명의 승객이 체크인하는데 걸리는 시간은 Tk초가 필요하며, 우리 대표단 멤버들은 그 숫자를 정확하게 알고있다. 처음에, 모든 데스크들은 다음 승객들을 받아드릴 준비가 되어있고, 대표단 멤버들이 줄에있는 유일한 사람들이다. 한명의 사람은 자신보다 앞에 줄선 사람이 이미 모두 나갔을 때 단 하나의 (체크인을 시작한곳) 유효한 데스크를 차지할 수 있다. (시작이 그렇고, 완료할 필요는 없다, 체크인을) 그 순간, 그 사람은 즉시 하나의 유효한 데스크를 차지하기 되고 (만약 하나만 있다면), 하지만 다른 (더빠른) 데스크가 유효하게 될 때 까지 기다리는 것을 선택 할 수도 있다. 우리의 대표단 멤버들은, 컴퓨터 공학 긱들이라서, 그들 모두가 체크인되는 시간이 가장 빨라지도록 하는 방법을 하기로 선택했다. 당신의 임무는 그 시간을 찾는것이다. 아래에 있는 첫번째 예제를 설명해보자. 여기에 두개의 데스크가 있고, 각각은 작업시간이 7초와 10초가 걸린다. 대표단이 6명의 사람으로 이어져있고, 처음에 두명이 바로 두개의 데스크를 차지한다. 시간 7에, 첫번째 데스크가 자유롭게 되고, 세번째 사람이 이것을 차지한다. 시간 10에, 네번째 사람이 두번째 데스크를 차지한다. 시간 14에 5번째 사람이 첫번째 데스크를 차지한다. 시간 20에, 두번째 데스크가 자유롭게 되지만, 여섯번째 사람은 다른 데스크를 기다리고 (시간 21) 첫번째 시간데스크가 가능하게 되면, 이것을 차지한다. 이러한 방법은, 체크인이 시간 28에 끝나게 된다. 만약 여섯번제 사람이 더 빠른 데스크를 기다리지 않고, 체크인을 시작했다면 총 시간은 30초가 걸렸을 것이다.
입력
첫번째 줄에 두개의 양의 정수, 데스크의 수 N (1<=N<=100 000), 그리고 대표단 사람의 수 M (1<=M<=1 000 000 000)이 주어진다. 각 N개의 줄에는 문제설명에서 주어진 수 Tk가 주어진다. (1<=Tk<=109)
출력
첫번째 그리고 단하나의 줄에 피룡한 최소 초를 출력한다.
힌트
배점형식 75점에 해당하는 점수에 대해서, M이 최대 300 000이다. 입력예제1 ``` 2 6 7 10 ``` 출력예제1 ``` 28 ``` 입력예제2 ``` 7 10 3 8 3 6 9 2 4 ``` 출력예제2 ``` 8 ```