P16410 [Algo Beat Contest 004 F] Fortune of Golden Cheese

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.

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 one line: the maximum amount of money $\mathrm{Jerry}$ can have left. If it is not enough, output `-1`.

#### 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