logo AlgoBeat OnlineJudge
登录 注册

#216213. [Algo Beat Contest 004 F] Fortune of Golden Cheese

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

老鼠 在一片草地发现了一块黄金奶酪,可惜 在那周围布下了 条电线。

但聪明的 请来了电工,不过由于电工非常的坑,要求每帮 解除一条电线的电便收他一些钱。

为了黄金奶酪,只能不惜拿出自己的全部积蓄。

草地是一个 的正方形,以左下角为原点。

老鼠 已经知道了黄金奶酪的坐标 并知道了电线的布局。

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

电工每解除一根电线的电就要收 元,而老鼠 的全部积蓄只有 元。

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

输入格式

第一行三个整数 ,表示电线的数量,电工要坑的钱和 的积蓄。

接下来 行,每行 个整数 表示第 条电线的两个端点的坐标。

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

输出格式

输出一行,即 最多还能余下多少钱,不够则输出 -1

样例

样例输入 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

样例输出 1

190

数据范围与提示

【样例解释】

草地这样的:

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

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

【数据范围】