Canoe Athletes

Interview

Time limit3sMemory limit256 MB

Summary

Pick one weight from each of four lists so the total is closest to the target, preferring the smaller total on ties.

Level: Medium5 of 10
Topics: Binary search, Sorting, Array
Solved: No attempts yet

Problem

The International Canoe Sprint Championship (ICSC) is about to open. The official boats certified by the ICSC are the C1, C2, and C4, where "C" stands for canoe and the number is how many paddlers ride in it. Canoe races are held on a straight, lane-divided course over calm water, and international events are split into the 200m, 500m, and 1000m distances.

A sports school plans to enter the ICSC C4 1000m event. The school has four classes with the same number of students each, and it forms a team by picking exactly one athlete from each class. The school's C4 boat performs best when the combined weight of its four athletes is as close as possible to a specific target value.

For example, suppose the target value is 300 and the students' weights in each class are:

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

Choosing 60, 75, 93, and 73 from the four classes gives a total weight of 301, the closest to the target 300. Sometimes two totals are equally close to the target. For instance, if the target is 200 and both 198 and 202 are achievable, each is 2 away from the target; in that case the smaller total is preferred, so 198 is chosen.

Given the boat's target value and the weights of the students in each class, pick one athlete from each of the four classes under the rule above and report the resulting total weight.

Input

Input is given on standard input. The first line contains the number of test cases $T$ .

The first line of each test case contains two integers $k$ and $n$ . Here $k$ ( $1 \le k \le 40{,}000{,}000$ ) is the boat's target value and $n$ ( $1 \le n \le 1{,}000$ ) is the number of students in each class.

The next four lines give the weights of the students in classes 1 through 4, with $n$ weights per line. Each weight is an integer between 1 and 10,000,000.

Output

For each test case, print the answer on its own line: the total weight of the four chosen athletes, that is, the achievable total closest to the target $k$ (and the smaller total when two are equally close).

Examples4

Example 1

Input

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

Expected output

301
8
31

Example 2
Input
```
1
100 1
10
20
30
5
```
Expected output
```
65
```
Example 3
Input
```
1
200 2
50 60
50 40
50 40
50 60
```
Expected output
```
200
```
Example 4
Input
```
1
10 2
3 7
1 1
2 2
2 2
```
Expected output
```
8
```