Description
지원이와 동현이, 그리고 민건이는 상자를 열기 위해 열쇠 세 개의 조합을 찾아야 한다. 각 열쇠는 특정한 번호를 가지고 있으며, 상자를 열기 위해 필요한 열쇠 세 개의 번호 합이 특정한 목푯값 T에 가까워야 상자가 열린다. 열쇠 번호는 정수 배열 형태로 제공되며, 세 사람은 정수 배열에서 숫자 세 개를 이용해 목푯값에 가장 가까운 조합을 찾아야 한다.
Input
첫 번째 줄: 테스트케이스 수 test가 입력된다.(1 <= test <= 20 인 정수)
두 번째 줄: 열쇠 번호 배열의 크기를 나타내는 정수 n이 입력된다.(3 ≤ n ≤ 100)
세 번째 줄: 열쇠 번호를 나타내는 정수 배열값들이 n개 주어진다.(이 값들은 1 이상 100 이하)
네 번째 줄: 세 숫자의 합이 접근해야 하는 목푯값을 나타내는 정수 t가 주어진다.(1 ≤ t ≤ 300)
이 처럼 두 번째 줄 ~ 네 번째 줄의 값들이 테스트케이스 수만큼 반복되어 입력된다.
Output
첫 번째 줄에 목푯값 t에 가장 가까운 세 숫자의 합이 출력된다. 두 번째 줄에 세 숫자를 오름차순으로 정렬하여 한 칸씩 띄어 출력한다.(만약 두 개 이상의 조합이 동일한 값으로 목푯값에 가까운 경우, 3개의 정수 중 가장 작은 숫자가 가장 작은 조합이, 그 값도 같은 경우에는 두 번째로 작은 숫자가 더 작은 조합이 출력되도록 한다. 만약 앞의 두 숫자를 제외한 세 번째 숫자가 조합으로 2개 이상 가능한 경우에는 그 중 작은 수를 출력한다.)
이 두 줄을 테스트케이스 수만큼 출력한다.
2
5
10 20 30 45 50
70
8
8 7 6 5 4 3 2 1
15