题目背景
某个夏天,18071 号工作室的 staff 集体转业了。辗转至年末,天依终于在 40312 号工作室拉到了合作。但是……看着编号的差距,按时到班可不是一件容易的事情。
七点半,闹铃声响起,早高峰即将迎接起床气!
题目描述
天依住在的城市像一个无穷大的曼哈顿。如果把城市地图放在平面直角坐标系中,任何一个整点 (x,y) 都是一个十字路口。天依家门口的十字路口为 (0,0),天依需要从这里出发,尽快抵达工作室所在的十字路口 (a,b)。每分钟,天依可以从她所在的十字路口 (x,y) 移动至 (x+1,y),(x−1,y),(x,y+1) 或者 (x,y−1)。
天依怎么会走路上班呢?她可以使用一辆很快很邪门的破自行车!骑上它,天依可以从 (x,y) 瞬间冲到 (x+l,y),(x,y+l),(x−l,y),(x,y−l) 四个位置中的一个,不花费任何时间。但为了避免破自行车散架,天依最多使用 k 次自行车。
那么,在破自行车的助力下,天依至少需要多少时间才能从 (0,0) 出发到达 (a,b) 呢?
因为工作室经常搬家,所以有多组测试数据。
输入格式
第一行一个整数 T,表示测试数据组数。
接下来 T 行,每行四个整数 a,b,k,l,分别表示工作室所在的十字路口的横纵坐标,自行车的使用次数限制和自行车的移动距离。
输出格式
输出 T 行,第 i 行一个整数,表示第 i 组数据中到达工作室的最小时间。
3
4 5 3 2
1 1 4 5
8 8 4 8
3
2
0
提示
样例解释:
我们使用 > 表示猛冲,→ 表示行走。
对于样例一,一种可能的移动方式是:(0,0)>(2,0)→(3,0)→(4,0)→(4,1)>(4,3)>(4,5)。
对于样例二,一种可能的移动方式是:(0,0)→(0,1)→(1,1)。
对于样例三,一种可能的移动方式是:(0,0)>(0,8)>(8,8)。
数据规模与约定
本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。
对于 100% 的数据,1≤T≤105,0≤a,b,k,l≤109。
对于不同的子任务,作如下约定:
子任务编号 |
T |
a,b,l |
k |
特殊性质 |
子任务分值 |
1 |
≤105 |
≤109 |
=0 |
无 |
15 |
2 |
≤10 |
≤10 |
10 |
3 |
≤109 |
≤20 |
15 |
4 |
≤103 |
20 |
5 |
≤105 |
≤109 |
a,b≤l |
15 |
6 |
无 |
25 |