Question 5 Rocky Bhai Java Solution

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.InputMismatchException;


public class Main implements Runnable {
    private InputReader in;
    private PrintWriter out;

    public static void main(String[] args) {
//      new Thread(new Template()).start();
        new Main().run();
    }

    public Main() {
        String id = getClass().getName().toLowerCase();
//      try {
//          System.setIn(new FileInputStream(id + ".in"));
//          System.setOut(new PrintStream(new FileOutputStream(id + ".out")));
//      } catch (FileNotFoundException e) {
//          throw new RuntimeException();
//      }
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);
    }

    public void run() {
        int numTests = in.readInt();
        for (int testNumber = 0; testNumber < numTests; testNumber++) {
            int m = in.readInt();
            int n = in.readInt();
            int k = in.readInt();
            int[] t = new int[m];
            int[] p = new int[m];
            for (int i = 0; i < m; i++)
                t[i] = in.readInt();
            for (int i = 0; i < m; i++)
                p[i] = in.readInt();
            int l = 0;
            int r = t[0] + (k - 1) * p[0];
            int[] q = new int[m];
            while (l < r) {
                int mm = (l + r) / 2;
                for (int i = 0; i < m; i++) {
                    if (mm < t[i])
                        q[i] = 0;
                    else
                        q[i] = (mm - t[i]) / p[i] + 1;
                }
                Arrays.sort(q);
                long cur = 0;
                for (int i = m - 1; i >= 0 && i >= m - n; i--)
                    cur += q[i];
                if (cur >= k)
                    r = mm;
                else
                    l = mm + 1;
            }
            out.println(l);
        }
        out.close();
    }

    private static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1000];
        private int curChar, numChars;

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

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

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

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

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

        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0)
                s = readLine0();
            return s;
        }

        public String readLine(boolean ignoreEmptyLines) {
            if (ignoreEmptyLines)
                return readLine();
            else
                return readLine0();
        }

        public BigInteger readBigInteger() {
            try {
                return new BigInteger(readString());
            } catch (NumberFormatException e) {
                throw new InputMismatchException();
            }
        }

        public char readCharacter() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public double readDouble() {
            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 < '0' || c > '9') {
                    if (c == 'e' || c == 'E') {
                        int e = readInt();
                        return res * Math.pow(10, e);
                    }
                    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') {
                        int e = readInt();
                        return res * Math.pow(10, e);
                    }
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
    }

}