import java.io.*;
import java.util.*;

public class Solution{
    FastReader in;
    PrintWriter out;
    Helper_class h;
    public static void main(String[] args) throws java.lang.Exception{
        new Solution().run();
    }
    void run() throws Exception{
        in=new FastReader(System.in);
        out = new PrintWriter(System.out);
        h = new Helper_class();
        int t = h.ni();
        for(int i = 1; i <= t; i++)
            solve(i);
        out.flush();
        out.close();
    }
    TreeMap<Long, Integer> tmap = new TreeMap<Long, Integer>();
    int n, m;
    boolean check(long threshold){
        int cnt = 0;
        long curr = threshold;
        TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
        for(Long hola : tmap.keySet()) {
            map.put(hola,  tmap.get(hola));
        }
        while(map.size() > 0){
            Long just_smaller = map.floorKey(curr);
            if(just_smaller == null){
                cnt++;
                curr = threshold;
                continue;
            }
            int freq = map.get(just_smaller);
            if(freq == 1)
                map.remove(just_smaller);
            else
                map.put(just_smaller, --freq);
            curr -= just_smaller;
        }
        cnt++;
        if(cnt <= m)
            return true;
        else
            return false;
    }
    void solve(int t){
        n = h.ni();
        long[] arr = new long[n];
        int i = 0;
        long max = 0, sum = 0;
        for(i = 0; i < n; i++){
            arr[i] = h.nl();
            max = Math.max(max, arr[i]);
            sum += arr[i];
            Integer x = tmap.get(arr[i]);
            if(x == null)
                tmap.put(arr[i], 1);
            else
                tmap.put(arr[i], ++x);
        }
        m = h.ni();
        long lo = max, hi = sum;
        while(lo <= hi){
            long mid = (lo + hi) >> 1;
            if(check(mid))
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        h.pn(hi + 1);
    }


    class Helper_class{

        void pn(Object o){out.println(o);}
        int ni(){return Integer.parseInt(in.next());}
        long nl(){return Long.parseLong(in.next());}
    }

    class FastReader{
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int peek() {
            if (numChars == -1)
                return -1;
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    return -1;
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar];
        }

        public void skip(int x) {
            while (x-- > 0)
                read();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public String nextString() {
            return next();
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public String nextLine() {
            StringBuffer buf = new StringBuffer();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r')
                    buf.appendCodePoint(c);
                c = read();
            }
            return buf.toString();
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public boolean hasNext() {
            int value;
            while (isSpaceChar(value = peek()) && value != -1)
                read();
            return value != -1;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}