Problem: There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful stones on the planet, and the Yaen people love to collect them. They bring the stones back home and make nice mobile arts of them to decorate their 2-dimensional living rooms.

In their 2-dimensional world, a mobile is defined recursively as follows:

* a stone hung by a string, or
* a rod of length 1 with two sub-mobiles at both ends; the rod is hung by a string at the center of gravity of sub-mobiles. When the weights of the sub-mobiles are n and m, and their distances from the center of gravity are a and b respectively, the equation n × a = m × b holds.


<image>


For example, if you got three stones with weights 1, 1, and 2, here are some possible mobiles and their widths:

<image>

Given the weights of stones and the width of the room, your task is to design the widest possible mobile satisfying both of the following conditions.

* It uses all the stones.
* Its width is less than the width of the room.



You should ignore the widths of stones.

In some cases two sub-mobiles hung from both ends of a rod might overlap (see the figure on the below). Such mobiles are acceptable. The width of the example is (1/3) + 1 + (1/4).


<image>



Input

The first line of the input gives the number of datasets. Then the specified number of datasets follow. A dataset has the following format.


r
s
w1
.
.
.
ws


r is a decimal fraction representing the width of the room, which satisfies 0 < r < 10. s is the number of the stones. You may assume 1 ≤ s ≤ 6. wi is the weight of the i-th stone, which is an integer. You may assume 1 ≤ wi ≤ 1000.

You can assume that no mobiles whose widths are between r - 0.00001 and r + 0.00001 can be made of given stones.

Output

For each dataset in the input, one line containing a decimal fraction should be output. The decimal fraction should give the width of the widest possible mobile as defined above. An output line should not contain extra characters such as spaces.

In case there is no mobile which satisfies the requirement, answer -1 instead.

The answer should not have an error greater than 0.00000001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

Example

Input

5
1.3
3
1
2
1
1.4
3
1
2
1
2.0
3
1
2
1
1.59
4
2
1
1
3
1.7143
4
1
2
3
5


Output

-1
1.3333333333333335
1.6666666666666667
1.5833333333333335
1.7142857142857142

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int N = 7, M = 1 << N;
int tr[M];          //-1: root, 0: no use, else:left value
int value[M];
int sumvalue[M];
double _left[M], _right[M], cur[M];   //具体的位置
bool st[N];
double r, ans;   int s;
double _r;
int q[N];
vector<double> que;

void dfs_value(int u){      //dfs求得左右子树的value
    if(tr[u] != -1){
        value[u] = tr[u];
        return;
    }
    dfs_value(u * 2);
    dfs_value(u * 2 + 1);
    value[u] = value[u * 2] + value[u * 2 + 1];
}


void update(){              //dfs进行更新ans
    int cnt = 1;
    int mark = 1;



    memcpy(value, tr, sizeof value);
    dfs_value(1);

    int u;
    double res = 0.0, t = 0.0;

    // 一路向左 加 一路向右
    double l = 0, r = 0;
    cur[1] = 0;
    for(int i = 1; i <= M; i++){
        if(tr[i] == -1){
            int x = 2 * i, y = 2 * i + 1;
            _left[i] = double(value[y]) / (value[x] + value[y]);
            _right[i] = double(value[x]) / (value[x] + value[y]);
            cur[x] = cur[i] - _left[i];
            cur[y] = cur[i] + _right[i];
            l = min(cur[x], l);
            r = max(cur[y], r);
        }
    }


    res = (r - l);
    if(res <= _r + 0.00000001){
        ans = max(ans, res);
    }

    cnt = 1;
    mark = 1;

    //cout<<"RES : "<<res<<endl;
    //que.push_back(res);
    /*printf("T  : %0.16f\n", r - l);
    printf("RES: %0.16f\n", res);
    cout<<"*************************\n";
    for(int i = 1; i < (2 << s); i++){
        printf("%d ", tr[i]);
        if(mark == i){
            cnt *= 2;
            mark += cnt;
            cout<<endl;
        }
    }
    cout<<"*************************\n";
    cnt = 1;
    mark = 1;
    cout<<"*************************\n";
    for(int i = 1; i < (2 << s); i++){
        printf("%d ", value[i]);
        if(mark == i){
            cnt *= 2;
            mark += cnt;
            cout<<endl;
        }
    }
    cout<<"*************************\n";*/

}

// 二叉树的线性便利
void dfs(int u, int surp, int need){    //need: 是现在需要的， surp 是剩余的
    if(need < surp) return;
    //if(u >= (2 << s))   return;
    //printf("U:%d, SURP:%d, NEED:%d\n", u, surp, need);
    if(need == 0){      //递归结束，填坑完毕
        //调用更新函数
        update();
        //cout<<"*************UPDATE*************"<<endl;
        return;
    }

    if(tr[u / 2] != -1){    //这个点不可以，下一个
        dfs(u + 1, surp, need);
        return;
    }


    if(surp < need){    //可以加一个杠
        int tmp = tr[u];
        tr[u] = -1;
        dfs(u + 1, surp + 1, need);
        tr[u] = tmp;
    }

    if(surp == 1 && need > 1)   return;     //一定要注意这一个，只剩一下一个位置，不可以放东西了,只允许加杠

    //不加杠
    for(int i = 1; i <= s; i++){
        if(st[i])   continue;
        st[i] = true;
        int tmp = tr[u];
        tr[u] = q[i];
        dfs(u + 1, surp - 1, need - 1);
        st[i] = false;
        tr[u] = tmp;
    }
    return;
}

int main()
{
    int T;  cin>>T;

    while(T--){
        cin>>r>>s;
        _r = r;
        for(int i = 1; i <= s; i++) scanf("%d", &q[i]);
        if(s == 1){
            if(0.0 <= r + 0.0000001){
                printf("%0.16f\n", 0.0);
            }else{
                cout<<-1<<endl;
            }
            continue;
        }

        memset(tr, 0, sizeof tr);   memset(st, false, sizeof st);
        ans = -1;
        tr[1] = -1;
        dfs(2, 2, s);

        /*for(int i = 0; i < que.size(); i++){
            printf("%0.6f\n", que[i]);
        }*/
        //printf("Ans: %0.6lf\n", ans);


        if(ans >= -0.001){
            printf("%0.16f\n", ans);
        }else{
            cout<<-1<<endl;
        }

    }
    return 0;
}