문제 설명
학교 식당에는 학생들을 위해 다양한 코너가 있습니다.
그러나 각 코너마다 음식을 주문하는데 걸리는 시간이 다르기 때문에 학생들은 각 코너의 대기열에 서서 주문을 해야 합니다.
한 코너에서는 오직 한 명만 주문을 받을 수 있습니다.
가장 앞에 서 있는 학생은 비어 있는 코너로 가서 주문을 할 수 있습니다.
하지만 학생들은 점심시간을 더 즐기고 싶기 때문에, 더 빨리 주문을 받는 코너가 있으면 기다렸다가 그 코너에 가서 주문을 합니다.
(학생들은 식성이 좋아서 어떤 코너든 상관없이 잘 먹습니다.)
모든 학생들의 주문을 받는데 걸리는 시간을 최소화하고 싶습니다.
학생 수와 학교 식당의 각 코너에서 한 명의 주문을 받는데 걸리는 시간이 입력으로 주어질 때, 모든 학생의 주문을 받는데 걸리는 시간의 최소값을 구해주세요.
입력 설명
첫 줄에는 테스트케이스 T(1 ≤ T ≤ 105)가 주어집니다.
그다음 줄부터 아래의 입력 정보들이 반복하여 주어집니다.
첫 줄에는 학교 식당을 이용하는 학생 수 A(1 ≤ A ≤ 109)와 코너의 개수 B(1 ≤ B ≤ 105)가 주어집니다.
다음 줄부터 코너마다 주문하는데 걸리는 시간 C(1 ≤ C ≤ 109)가 주어집니다.
출력 설명
모든 학생들의 주문을 받는데 걸리는 최소 시간을 출력해주세요.