P11768 破自行车

某个夏天，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)$ 呢? 因为工作室经常搬家，所以有多组测试数据。

无

无

### 样例解释： 我们使用 $>$ 表示猛冲，$\to$ 表示行走。 对于样例一，一种可能的移动方式是：$(0,0)>(2,0)\to(3,0)\to(4,0)\to(4,1)>(4,3)>(4,5)$。 对于样例二，一种可能的移动方式是：$(0,0)\to(0,1)\to(1,1)$。 对于样例三，一种可能的移动方式是：$(0,0)>(0,8)>(8,8)$。 ### 数据规模与约定 **本题采用捆绑测试。** 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。 对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$0 \leq a,b,k,l\leq 10^{9}$。 对于不同的子任务，作如下约定： | 子任务编号 | $T$ | $a,b,l$ | $k$ | 特殊性质 | 子任务分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le10^5$ | $\le10^9$ | $=0$ | 无 | $15$ | | $2$ | $\le10$ | $\le10$ | $\le10$ | 无 | $10$ | | $3$ | $\le10$ | $\le10^9$ | $\le20$ | 无 | $15$ | | $4$ | $\le10$ | $\le10^9$ | $\le10^3$ | 无 | $20$ | | $5$ | $\le10^5$ | $\le10^9$ | $\le10^9$ | $a,b\le l$ | $15$ | | $6$ | $\le10^5$ | $\le10^9$ | $\le10^9$ | 无 | $25$ |