Problem: Vasya plays the Plane of Tanks. The tanks in this game keep trying to finish each other off. But your "Pedalny" is not like that... He just needs to drive in a straight line from point A to point B on the plane. Unfortunately, on the same plane are n enemy tanks. We shall regard all the tanks as points. At the initial moment of time Pedalny is at the point A. Enemy tanks would be happy to destroy it immediately, but initially their turrets are tuned in other directions. Specifically, for each tank we know the initial rotation of the turret ai (the angle in radians relative to the OX axis in the counterclockwise direction) and the maximum speed of rotation of the turret wi (radians per second). If at any point of time a tank turret will be aimed precisely at the tank Pedalny, then the enemy fires and it never misses. Pedalny can endure no more than k shots. Gun reloading takes very much time, so we can assume that every enemy will produce no more than one shot. Your task is to determine what minimum speed of v Pedalny must have to get to the point B. It is believed that Pedalny is able to instantly develop the speed of v, and the first k shots at him do not reduce the speed and do not change the coordinates of the tank.

Input

The first line contains 4 numbers – the coordinates of points A and B (in meters), the points do not coincide. On the second line number n is given (1 ≤ n ≤ 104). It is the number of enemy tanks. Each of the following n lines contain the coordinates of a corresponding tank xi, yi and its parameters ai and wi (0 ≤ ai ≤ 2π, 0 ≤ wi ≤ 100). Numbers ai and wi contain at most 5 digits after the decimal point. All coordinates are integers and their absolute values do not exceed 105. Enemy tanks can rotate a turret in the clockwise as well as in the counterclockwise direction at the angular speed of not more than wi. It is guaranteed that each of the enemy tanks will need at least 0.1 seconds to aim at any point of the segment AB and each of the enemy tanks is posistioned no closer than 0.1 meters to line AB. On the last line is given the number k (0 ≤ k ≤ n).

Output

Print a single number with absolute or relative error no more than 10 - 4 — the minimum required speed of Pedalny in meters per second.

Examples

Input

0 0 10 0
1
5 -5 4.71238 1
0


Output

4.2441


Input

0 0 10 0
1
5 -5 4.71238 1
1


Output

0.0000

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Tanks implements Runnable {
    class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    Point readPoint() throws IOException {
        int x = nextInt();
        int y = nextInt();
        return new Point(x, y);
    }

    private void solve() throws IOException {
        Point A = readPoint();
        Point B = readPoint();
        int n = nextInt();
        Point[] tank = new Point[n];
        double[] alpha = new double[n];
        double[] w = new double[n];
        for (int i = 0; i < n; ++i) {
            tank[i] = readPoint();
            alpha[i] = nextDouble();
            if (alpha[i] > Math.PI) alpha[i] -= 2 * Math.PI;
            w[i] = nextDouble();
        }
        int canSuffer = nextInt();
        double[] maxHit = new double[n + 1];
        for (int i = 0; i < n; ++i) {
            maxHit[i] = processTank(A, B, tank[i], alpha[i], w[i]);
        }
        Arrays.sort(maxHit);
        writer.println(maxHit[n - canSuffer]);
    }

    private double processTank(Point A, Point B, Point tank, double alpha, double w) {
        if (w == 0)
            return 0;
        return Math.max(process(A, B, tank, alpha, w), process(A, B, tank, alpha, -w));
    }

    private double process(Point a, Point b, Point tank, double alpha, double w) {
        double alphaA = Math.atan2(a.y - tank.y, a.x - tank.x);
        double alphaB = Math.atan2(b.y - tank.y, b.x - tank.x);
        if (Math.signum(alphaA - alpha) != Math.signum(w)) alphaA += Math.PI * 2 * Math.signum(w);
        if (Math.signum(alphaB - alpha) != Math.signum(w)) alphaB += Math.PI * 2 * Math.signum(w);
        double tA = (alphaA - alpha) / w;
        double tB = (alphaB - alpha) / w;
        double dy = b.y - a.y;
        double dx = b.x - a.x;
        double dist = Math.sqrt(dx * dx + dy * dy);
        if (tB <= tA) {
            return dist / tB;
        } else {
            double best = 0;
            double bestVal = 0;
            double res = dist / tB;
            for (int i = 0; i <= 100; ++i) {
                double middle = i / 100.0;
                double x = a.x + middle * dx;
                double y = a.y + middle * dy;
                double alphaM2 = Math.atan2(y - tank.y, x - tank.x);
                if (Math.signum(alphaM2 - alpha) != Math.signum(w)) alphaM2 += Math.PI * 2 * Math.signum(w);
                double tM = (alphaM2 - alpha) / w;
                double cur = middle * dist / tM;
                res = Math.max(res, cur);
                if (cur > bestVal) {
                    bestVal = cur;
                    best = middle;
                }
            }
            double left = Math.max(0, best - 0.03);
            double right = Math.min(1, best + 0.03);
            for (int i = 0; i < 300; ++i) {
                double middle2;
                double tM2;
                {
                    middle2 = (left + 2 * right) / 3;
                    double x = a.x + middle2 * dx;
                    double y = a.y + middle2 * dy;
                    double alphaM2 = Math.atan2(y - tank.y, x - tank.x);
                    if (Math.signum(alphaM2 - alpha) != Math.signum(w)) alphaM2 += Math.PI * 2 * Math.signum(w);
                    tM2 = (alphaM2 - alpha) / w;
                }
                double middle1;
                double tM1;
                {
                    middle1 = (2 * left + right) / 3;
                    double x = a.x + middle1 * dx;
                    double y = a.y + middle1 * dy;
                    double alphaM1 = Math.atan2(y - tank.y, x - tank.x);
                    if (Math.signum(alphaM1 - alpha) != Math.signum(w)) alphaM1 += Math.PI * 2 * Math.signum(w);
                    tM1 = (alphaM1 - alpha) / w;
                }
                double valM1 = dist * middle1 / tM1;
                double valM2 = dist * middle2 / tM2;
                res = Math.max(res, valM1);
                res = Math.max(res, valM2);
                if (valM1 > valM2) {
                    right = middle2;
                } else {
                    left = middle1;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        new Tanks().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}