#include <iostream>
#include <vector>


void print(std::vector<std::vector<int>> &arr,int B, std::vector<int> &arr2)
{
    int n = arr.size();

    int* indices = new int[n];

    for (int i = 0; i < n; i++)
        indices[i] = 0;

    while (1) {
        int suma=0;
        for (int i = 0; i < n; i++)
            {
               suma+=arr[i][indices[i]];
            }
        if(B-suma>=0)
        {
            arr2.push_back(suma);

        }

        int next = n - 1;
        while (next >= 0 &&
              (indices[next] + 1 >= arr[next].size()))
            next--;
        if (next < 0)
            return;

        indices[next]++;

        for (int i = next + 1; i < n; i++)
            indices[i] = 0;
    }
}


int main()
{
    std::ios::sync_with_stdio(false);

    int T,B,N;

    std::cin>>T;

    for(int z=0;z<T;z++)
    {
        B=0;N=0;
     std::cin>>B>>N;

     std::vector<std::vector<int>> arr;
     std::vector<int> arr2;

    for(int i=0;i<N;i++)
    {
       int temp;
       std::cin>>temp;
       std::vector<int> row;
       for(int i=0;i<temp;i++)
       {
           row.push_back(0);
       }
       arr.push_back(row);
    }

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<arr.at(i).size();j++)
        {
            int temp;
            std::cin>>temp;
            arr.at(i).at(j)=temp;
        }
    }

    print(arr,B,arr2);
    arr.clear();
    int biggest=0;
    for(int i=0;i<arr2.size();i++)
    {
        if(biggest<=arr2.at(i)) {biggest=arr2[i];}
    }
    std::cout<<biggest<<std::endl;
    arr2.clear();
    }

    return 0;
}