Problem Description

The mouse $\mathrm{Jerry}$ found a piece of golden cheese in a grassland, but unfortunately $\mathrm{Tom}$ set up $n$ electric wires around it.

The clever $\mathrm{Jerry}$ hired an electrician. However, the electrician is very dishonest and charges some money each time he helps $\mathrm{Jerry}$ cut off the power of one wire.

For the golden cheese, $\mathrm{Jerry}$ has to spend all his savings.

The grassland is a $10^6 \times 10^6$ square, with the bottom-left corner as the origin.

The mouse $\mathrm{Jerry}$ already knows the coordinates $x, y$ of the golden cheese and also knows the layout of the wires.

Both ends of each wire are tied to poles on the boundary of the grassland, with endpoints at $(a, b)$ and $(c, d)$. In particular, no wire is collinear with the boundary of the grassland, and the mouse will not get electrocuted when standing at an endpoint of a wire.

The electrician charges $k$ dollars for disabling one wire, and $\mathrm{Jerry}$ has only $m$ dollars in total.

Although $\mathrm{Jerry}$ is clever, he is not as experienced as the electrician at cheating money. He might focus only on getting the golden cheese and end up owing a lot of debt. So please help him: if the required payment exceeds the mouse’s savings, make him give up the cheese and output -1. Otherwise, compute the maximum amount of money he can have left while reaching the cheese without getting electrocuted, to decide today’s dinner.

Input Format

The first line contains three integers $n, k, m$, representing the number of wires, the money the electrician charges, and $\mathrm{Jerry}$’s savings.

The next $n$ lines each contain $4$ integers $a, b, c, d$, representing the coordinates of the two endpoints of the $i$-th wire.

The next line contains two floating-point numbers $x, y$, representing the coordinates of the treasure.

Output Format

Output one line: the maximum amount of money $\mathrm{Jerry}$ can have left. If it is not enough, output -1.

11 5 200
0 750000 250000 1000000
0 650000 450000 1000000
0 500000 500000 1000000
250000 0 750000 1000000
500000 0 1000000 500000
0 250000 1000000 500000
450000 1000000 1000000 500000
250000 1000000 750000 0
0 750000 500000 0
0 650000 300000 0
0 200000 500000 0
300200.0 500000.0

190

Hint

Sample Explanation

The grassland looks like this:

The orange point is the golden cheese, and the black lines are the wires. If $\mathrm{Jerry}$ wants to get the cheese, he needs the electrician to disable one of the two wires marked in purple on the left or on the right.

This costs $10$ dollars. The mouse originally had $200$ dollars, and now has $190$ dollars left. He can get the golden cheese and still enjoy a hearty dinner.

Constraints

• $0 \le n \le 10^6$.
• $0 \le x, y, a, b, c, d \le 10^6$.
• $0 \le k \le 10^5$, $0 \le m \le 10^{12}$.

Translated by ChatGPT 5