입국 심사
시간 제한1초메모리 제한128 MB
N개 창구의 처리 시간과 M명의 대기자가 주어질 때 모든 사람의 심사를 마치는 최소 시간을 이분 탐색으로 구합니다.
문제
M명의 여행객이 입국 심사를 받기 위해 한 줄로 서 있다. 입국 심사대는 N개이고, k번째 심사대는 한 사람을 심사하는 데 Tk초가 걸린다.
처음에는 모든 심사대가 비어 있고 준비가 끝난 상태다. 한 심사대는 동시에 한 사람만 처리할 수 있다. 줄의 맨 앞 사람은 비어 있는 심사대로 이동할 수 있지만, 반드시 즉시 이동할 필요는 없다. 더 빨리 끝날 심사대를 기다렸다가 이동해도 된다.
모든 여행객이 심사를 마치는 데 필요한 최소 시간을 구하라.
입력
첫째 줄에 심사대 수 N과 여행객 수 M이 주어진다. (1 <= N <= 100,000, 1 <= M <= 1,000,000,000)
다음 N개 줄에는 각 심사대가 한 사람을 심사하는 데 걸리는 시간 Tk가 주어진다. (1 <= Tk <= 1,000,000,000)
출력
모든 여행객이 심사를 마치는 데 걸리는 최소 시간을 출력한다.