공장에서 생산된 \(M\)개의 제품이 품질 검사를 기다리고 있다. 공장에는 제품을 검사할 수 있는 검사 장비가 \(N\)대 있으며, 장비마다 제품 한 개를 검사하는 데 걸리는 시간이 다르다. \(k\)번 검사 장비가 제품 한 개를 검사하는 데에는 \(T_k\)초가 걸린다.

처음에는 모든 검사 장비가 비어 있으며 즉시 검사를 시작할 수 있다. 하나의 검사 장비는 한 번에 제품 하나만 검사할 수 있다. 검사를 기다리는 제품은 비어 있는 검사 장비에서 바로 검사를 시작할 수도 있고, 더 빠른 검사 장비가 빌 때까지 기다린 뒤 그 장비에서 검사를 받을 수도 있다.

모든 제품의 품질 검사를 마치는 데 걸리는 시간의 최솟값을 구하여라.

입력

첫째 줄에 검사 장비의 수 \(N\)과 검사할 제품의 수 \(M\)이 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에는 \(k\)번 검사 장비가 제품 하나를 검사하는 데 걸리는 시간 \(T_k\)가 주어진다.

출력

모든 제품의 품질 검사를 마치는 데 걸리는 시간의 최솟값을 출력한다.

제한 사항

• \(1 \le N \le 100,000\)
• \(1 \le M \le 1,000,000,000\)
• \(1 \le T_k \le 1,000,000,000\)

예제 입력 1

3 11
4
7
10

예제 출력 1

24

예제 설명 1

\(24\)초 동안 각 검사 장비가 검사할 수 있는 제품의 수는 차례대로 \(6\)개, \(3\)개, \(2\)개이다. 따라서 총 \(11\)개의 제품을 모두 검사할 수 있다.

반면 \(23\)초 동안 검사할 수 있는 제품의 수는 각각 \(5\)개, \(3\)개, \(2\)개로 총 \(10\)개뿐이다. 따라서 모든 제품의 검사를 마치는 데 걸리는 시간의 최솟값은 \(24\)초이다.

예제 입력 2

4 15
2
5
7
11

예제 출력 2

18