#8175. 「省选联考 2024」季风 省选/NOI−

题目背景

生活在二维平面的小 X 准备拜访小 Y，但由于气候的变化，平面上刮起了季风。小 X 想知道季风的影响下，TA 至少要多少天能够到达小 Y 的家，但小 X 也是第一次遇见这种怪事，所以请精通算法的你来帮忙。

题目描述

给定 和 个整数 。

找到最小的非负整数 ，使得存在 个实数 满足以下条件，或报告不存在这样的 ：

• ；
• ；
• 。

特别地， 时，认为 和 均为 。

本题有多组测试数据。输入的第一行一个整数 表示测试数据组数。

对于每组测试数据，

• 第一行四个整数 ；
• 接下来 行，第 行两个整数 。

对于每组测试数据输出一行一个整数，如果存在满足题意的 ，输出其最小可能值，否则输出 。

样例输入 1

4
1 2 2 2
1 1
1 2 -2 -2
1 1
1 2 0 0
1 1
2 100000000 100000000 100000000
-99999999 0
-100000000 0

样例输出 1

1
-1
0
399999999

【样例 1 解释】

该组样例共有四组测试数据。

• 对于第一组测试数据，取 ， 满足条件，可以证明不存在更小的 满足条件；
• 对于第二组测试数据，可以证明不存在任何非负整数 满足条件；
• 对于第三组测试数据，取 满足条件，可以证明不存在更小的 满足条件。

【样例 2】

见附件中的 wind2.in/ans。

该组样例共有八十组测试数据，所有测试数据均满足 ，其中测试数据 满足特殊性质 A， 满足特殊性质 B， 满足特殊性质 C。

【样例 3】

见附件中的 wind3.in/ans。

该组样例共有六十组测试数据，所有测试数据均满足 ，其中测试数据 满足特殊性质 A， 满足特殊性质 B。

【子任务】

设 为单个测试点内所有测试数据 的和。对于所有测试数据：

• ；
• ，；
• 。

• 特殊性质 A：，；
• 特殊性质 B：；
• 特殊性质 C：。

【提示】

本题输入文件较大，请使用较为快速的输入方式。