#P11768. 破自行车

破自行车

题目背景

某个夏天,18071 号工作室的 staff 集体转业了。辗转至年末,天依终于在 40312 号工作室拉到了合作。但是……看着编号的差距,按时到班可不是一件容易的事情。

七点半,闹铃声响起,早高峰即将迎接起床气!

题目描述

天依住在的城市像一个无穷大的曼哈顿。如果把城市地图放在平面直角坐标系中,任何一个整点 (x,y)(x,y) 都是一个十字路口。天依家门口的十字路口为 (0,0)(0,0),天依需要从这里出发,尽快抵达工作室所在的十字路口 (a,b)(a,b)。每分钟,天依可以从她所在的十字路口 (x,y)(x,y) 移动至 (x+1,y)(x+1,y)(x1,y)(x-1,y)(x,y+1)(x,y+1) 或者 (x,y1)(x,y-1)

天依怎么会走路上班呢?她可以使用一辆很快很邪门的破自行车!骑上它,天依可以从 (x,y)(x,y) 瞬间冲到 (x+l,y)(x+l,y)(x,y+l)(x,y+l)(xl,y)(x-l,y)(x,yl)(x,y-l) 四个位置中的一个,不花费任何时间。但为了避免破自行车散架,天依最多使用 kk 次自行车。

那么,在破自行车的助力下,天依至少需要多少时间才能从 (0,0)(0,0) 出发到达 (a,b)(a,b) 呢?

因为工作室经常搬家,所以有多组测试数据。

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来 TT 行,每行四个整数 a,b,k,la,b,k,l,分别表示工作室所在的十字路口的横纵坐标,自行车的使用次数限制和自行车的移动距离。

输出格式

输出 TT 行,第 ii 行一个整数,表示第 ii 组数据中到达工作室的最小时间。

3
4 5 3 2
1 1 4 5
8 8 4 8
3
2
0

提示

样例解释:

我们使用 >> 表示猛冲,\to 表示行走。

对于样例一,一种可能的移动方式是:(0,0)>(2,0)(3,0)(4,0)(4,1)>(4,3)>(4,5)(0,0)>(2,0)\to(3,0)\to(4,0)\to(4,1)>(4,3)>(4,5)

对于样例二,一种可能的移动方式是:(0,0)(0,1)(1,1)(0,0)\to(0,1)\to(1,1)

对于样例三,一种可能的移动方式是:(0,0)>(0,8)>(8,8)(0,0)>(0,8)>(8,8)

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 100%100\% 的数据,1T1051 \leq T \leq 10^50a,b,k,l1090 \leq a,b,k,l\leq 10^{9}

对于不同的子任务,作如下约定:

子任务编号 TT a,b,la,b,l kk 特殊性质 子任务分值
11 105\le10^5 109\le10^9 =0=0 1515
22 10\le10 10\le10 1010
33 109\le10^9 20\le20 1515
44 103\le10^3 2020
55 105\le10^5 109\le10^9 a,bla,b\le l 1515
66 2525