카누 선수

국제 카누 스프린트 선수권 대회(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$에 가장 가까운 (거리가 같으면 더 작은) 합을 출력합니다.