Fujiyama Thursday

면접 대비

시간 제한1초메모리 제한1024 MB

요약

차량별 도착 시간과 참가자별 식사 속도가 주어졌을 때, 참가자 네 명씩 차량에 배정해 모든 참가자가 식사를 마치는 최소 시간을 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

지난 1년 동안 UCF 프로그래밍 팀원들은 Fujiyama Sushi에서 매주 저녁 식사를 해 왔다. 보통 팀원들은 모두 도착할 때까지 기다렸다가 식사를 시작한다. 그런데 캠퍼스 북쪽에서 온 현명한 팀 코치는 늘 이렇게 말한다. "지역 예선이 다가온다." 이 경고를 듣고 팀원들은 준비에 더 많은 시간을 써야 한다. 연습 시간을 늘리기 위해 팀원들은 도착하는 대로 식사를 시작한다. 다만 모두 식사를 마칠 때까지는 Fujiyama를 떠나기 위해 기다린다.

팀원들이 타는 차에는 정확히 4명이 탄다. 차마다 Fujiyama에 도착하는 데 걸리는 시간이 다를 수 있고, 팀원마다 식사 속도도 다를 수 있으므로 팀원을 차에 배정하는 방식이 중요하다. 모든 팀원은 어떤 차든 운전할 수 있으므로 어느 팀원이든 어느 차에든 배정할 수 있다.

각 차가 도착하는 데 걸리는 시간과 각 팀원의 식사 속도가 주어졌을 때, 팀원을 차에 최적으로 배정했을 때 모든 팀원이 식사를 마치는 데 걸리는 최소 시간을 구하시오.

입력

첫 줄에는 Fujiyama Sushi에 간 횟수를 나타내는 양의 정수 $n$ 이 주어진다. 각 회차는 세 줄로 표현된다. 각 회차의 첫 줄에는 Fujiyama에 가는 차의 수 $c$ ( $1 \le c \le 50$ )가 하나의 정수로 주어진다. 둘째 줄에는 $i$ 번째 차가 Fujiyama에 도착하는 데 걸리는 시간(분) $d_i$ ( $1 \le d_i \le 45$ )가 $c$ 개의 정수로 주어진다. 셋째 줄에는 $j$ 번째 팀원이 식사를 마치는 데 걸리는 시간(분) $t_j$ ( $1 \le t_j \le 75$ )가 $4c$ 개의 정수로 주어진다.

출력

각 회차마다 먼저 "Trip #d: " 머리말을 출력한다. 여기서 $d$ 는 1부터 시작하는 회차 번호이다. 이어서 모든 팀원이 식사를 마치는 데 걸리는 최소 시간(분)을 정수 하나로 출력한다. 출력 형식은 예시 출력에 나온 형식을 따른다.

예제1

예제 1

입력

3
1
40
1 2 3 4
2
10 20
5 6 3 4 8 9 1 2
3
15 20 20
10 10 10 10 20 20 20 20 30 30 30 30

예상 출력

Trip #1: 44
Trip #2: 24
Trip #3: 45