카누 선수

면접 대비

시간 제한3초메모리 제한256 MB

요약

네 목록에서 하나씩 골라 합이 목표에 가장 가깝게 하고 동점이면 작은 합을 선택합니다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

국제 카누 스프린트 선수권 대회(International Canoe Sprint Championship, ICSC)가 곧 개막합니다. ICSC가 공인하는 공식 보트는 C1, C2, C4 세 종류이며, "C"는 카누를, 숫자는 노를 젓는 사람의 수를 뜻합니다. 카누 경주는 잔잔한 물 위에 여러 레인으로 나뉜 직선 코스에서 진행되고, 국제 경기는 200m, 500m, 1000m로 구분합니다.

한 스포츠 학교가 ICSC의 C4 1000m 경기에 출전하려고 합니다. 이 학교에는 학생 수가 서로 같은 4개의 반이 있고, 각 반에서 선수 1명씩을 뽑아 한 팀을 구성합니다. 학교가 가진 C4 보트는 네 선수의 몸무게 합이 어떤 목표값에 가까울수록 최고의 성능을 냅니다.

예를 들어 목표값이 300이고 각 반 학생들의 몸무게가 다음과 같다고 합시다.

1반: 60, 52, 80, 40
2반: 75, 68, 88, 63
3반: 48, 93, 48, 54
4반: 56, 73, 49, 75

각 반에서 60, 75, 93, 73을 고르면 몸무게 합이 301이 되어 목표값 300에 가장 가깝습니다. 어떤 경우에는 목표값에서 같은 거리에 있는 두 개의 합이 나올 수 있습니다. 예를 들어 목표값이 200일 때 몸무게 합으로 198과 202가 모두 가능하다면, 둘 다 목표값에서 2만큼 떨어져 있습니다. 이런 경우에는 더 작은 합이 경기에 더 적합하므로 198을 선택합니다.

보트의 목표값과 각 반 학생들의 몸무게가 주어질 때, 위 규칙에 따라 네 반에서 각각 한 명씩 골랐을 때의 몸무게 합을 구하세요.

입력

입력은 표준 입력으로 주어집니다. 첫 줄에 테스트 케이스의 개수 $T$ 가 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $k$ 와 $n$ 이 주어집니다. $k$ ( $1 \le k \le 40{,}000{,}000$ )는 보트의 목표값이고, $n$ ( $1 \le n \le 1{,}000$ )은 각 반의 학생 수입니다.

이어지는 네 줄에는 1반부터 4반까지 각 반 학생들의 몸무게가 한 줄에 $n$ 개씩 주어집니다. 각 몸무게는 1 이상 10,000,000 이하의 정수입니다.

출력

각 테스트 케이스마다 답을 한 줄에 출력합니다. 그 줄에는 선수로 선택된 네 학생의 몸무게 합, 즉 목표값 $k$ 에 가장 가까운 (거리가 같으면 더 작은) 합을 출력합니다.

예제4

예제 1

입력

3
300 4
60 52 80 40
75 68 88 63
48 93 48 54
56 73 49 75
8 3
1 2 3
1 2 3
1 2 3
1 2 3
32 2
2 5
9 4
10 20
4 2

예상 출력

301
8
31

예제 2
입력
```
1
100 1
10
20
30
5
```
예상 출력
```
65
```
예제 3
입력
```
1
200 2
50 60
50 40
50 40
50 60
```
예상 출력
```
200
```
예제 4
입력
```
1
10 2
3 7
1 1
2 2
2 2
```
예상 출력
```
8
```