입국 심사

M명의 여행객이 입국 심사를 받기 위해 한 줄로 서 있다. 입국 심사대는 N개이고, k번째 심사대는 한 사람을 심사하는 데 Tk초가 걸린다.

처음에는 모든 심사대가 비어 있고 준비가 끝난 상태다. 한 심사대는 동시에 한 사람만 처리할 수 있다. 줄의 맨 앞 사람은 비어 있는 심사대로 이동할 수 있지만, 반드시 즉시 이동할 필요는 없다. 더 빨리 끝날 심사대를 기다렸다가 이동해도 된다.

모든 여행객이 심사를 마치는 데 필요한 최소 시간을 구하라.

첫째 줄에 심사대 수 N과 여행객 수 M이 주어진다. (1 <= N <= 100,000, 1 <= M <= 1,000,000,000)

다음 N개 줄에는 각 심사대가 한 사람을 심사하는 데 걸리는 시간 Tk가 주어진다. (1 <= Tk <= 1,000,000,000)

모든 여행객이 심사를 마치는 데 걸리는 최소 시간을 출력한다.