Wizards Unite
시간 제한2초메모리 제한512 MB
상자 n개의 개방 시간과 재사용 가능한 황금 열쇠 하나, 한 번만 쓸 수 있는 은 열쇠 k개가 주어질 때, 열쇠를 병렬로 써서 모든 상자를 여는 최소 시간을 구한다.
문제
안녕, 꼬마 마법사! 네 모험이 여기서 시작된다. 하지만 시작하기 전에 네가 자격이 있는지 증명해야 한다. 이 시험을 통과할 수 있겠니?
너에게는 마법 세계의 신비가 담겼을지도 모르는 낡은 상자가 잔뜩 있다. 가지고 있는 열쇠로 그 상자들을 전부 열고 싶다.
열쇠함에는 황금 열쇠 하나와 은 열쇠 k개가 있다. 어떤 열쇠든 어떤 상자든 열 수 있지만, 은 열쇠는 각각 한 번만 쓸 수 있고, 황금 열쇠는 여러 번 쓸 수 있다. 상자마다 여는 데 걸리는 시간을 알고 있다. 하나의 열쇠로 여러 상자를 동시에 열 수는 없다. 어떤 열쇠로 상자를 열기 시작했다면, 그 상자가 다 열릴 때까지 기다려야 그 열쇠를 다시 쓸 수 있다(물론 다시 쓸 수 있는 것은 황금 열쇠뿐이다). 반면 서로 다른 열쇠로 서로 다른 상자를 동시에 열 수 있으므로, 여러 상자를 같은 시각에 열고 있는 상황이 가능하다(여기서 설명한 황금 열쇠와 은 열쇠로 상자를 여는 방식은 실제로 게임 “Wizards Unite”에 존재한다. 이 문제를 풀며 얻은 통찰을 게임에서 활용해도 된다).
모든 상자를 여는 데 필요한 최소 시간은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 z가 주어진다. 그다음에 각 테스트 케이스의 설명이 이어진다.
각 테스트 케이스의 첫 줄에는 두 정수 n과 k가 주어진다(0 ≤ k < n ≤ 105). n은 상자의 수, k는 은 열쇠의 수다.
각 테스트 케이스의 둘째 줄에는 n개의 정수 ti가 주어진다(0 ≤ ti ≤ 109). 각 ti는 i번째 상자를 여는 데 필요한 시간이다.
모든 테스트 케이스의 상자 수 합은 106을 넘지 않는다.
출력
각 테스트 케이스마다 모든 상자를 여는 데 필요한 최소 시간을 나타내는 정수 하나를 한 줄에 출력한다.