题目描述

老鼠 $\mathrm{Jerry}$ 在一片草地发现了一块黄金奶酪，可惜 $\mathrm{Tom}$ 在那周围布下了 $n$ 条电线。

但聪明的 $\mathrm{Jerry}$ 请来了电工，不过由于电工非常的坑，要求每帮 $\mathrm{Jerry}$ 解除一条电线的电便收他一些钱。

$\mathrm{Jerry}$ 为了黄金奶酪，只能不惜拿出自己的全部积蓄。

草地是一个 $10^6\times 10^6$ 的正方形，以左下角为原点。

老鼠 $\mathrm{Jerry}$ 已经知道了黄金奶酪的坐标 $x,y$ 并知道了电线的布局。

电线的两端都绑在草地边缘的柱子上，两端的坐标分别为 $a,b$ 和 $c,d$ 。特别地，不会有任何一条电线与草地边缘共线，且老鼠站在一条电线的端点上时并不会触电。

电工每解除一根电线的电就要收 $k$ 元，而老鼠 $\mathrm{Jerry}$ 的全部积蓄只有 $m$ 元。

$\mathrm{Jerry}$ 虽然聪明，但却没有电工那丰富的骗钱经验厉害，可能光顾着拿黄金奶酪，结果欠了电工一屁股债，所以请你帮帮他，如果要收的钱超出了老鼠的积蓄，就让他放弃奶酪，输出 -1 ，否则帮他算出在不被电到的情况下他最多还能余下多少钱，来决定今天的晚餐。

输入格式

第一行三个整数 $n,k,m$，表示电线的数量，电工要坑的钱和 $\mathrm{Jerry}$ 的积蓄。

接下来 $n$ 行，每行 $4$ 个整数 $a,b,c,d$ 表示第 $i$ 条电线的两个端点的坐标。

接下来一行两个浮点数 $x,y$ 表示宝藏的坐标。

输出格式

输出一行，即 $\mathrm{Jerry}$ 最多还能余下多少钱，不够则输出 -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

提示

【样例解释】

草地这样的：

橙色点是黄金奶酪，黑色线是电线，如果 $\mathrm{Jerry}$ 想要拿到奶酪，则需要电工断掉左边或右边紫色标记的两条电线，

要花 $10$ 元，老鼠原本有 $200$ 元，现在还有 $190$ 元，不仅能拿到黄金奶酪，也依旧能够吃上一顿丰盛的晚餐。

【数据范围】

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