P11768 Broken Bicycle

Once in a summer, the entire staff of Studio 18071 transferred to new careers collectively. By the end of the year, Tianyi finally secured a collaboration in Studio 40312. However... Judging from the far cry in the studio numbers, getting to work on time was no easy task. At 7:30 a.m., the alarm clock rang, signaling the dawn of the morning rush hour and the impending battle against the grogginess of waking up!

The city where Tianyi lives is like an infinitely large Manhattan. If we place the city map on a Cartesian coordinate system, any **integer point** $(x,y)$ represents an intersection. Tianyi's doorstep intersection is at $(0,0)$, and she needs to start from here and reach the intersection $(a,b)$ of the studio as soon as possible. Every minute, Tianyi can move from her current intersection $(x,y)$ to $(x+1,y)$, $(x-1,y)$, $(x,y+1)$, or $(x,y-1)$. But why would Tianyi walk to work? She has a very fast and mysterious broken bicycle! With it, Tianyi can instantly charge from $(x,y)$ to any one of the four positions $(x+l,y)$, $(x,y+l)$, $(x-l,y)$, $(x,y-l)$, without spending any time. However, to prevent the broken bicycle from falling apart, Tianyi can only use it up to $k$ times. So, with the help of the broken bicycle, what is the minimum time Tianyi needs to travel from $(0,0)$ to $(a,b)$? Due to the frequent moving of the studio, there are multiple test cases.

N/A

N/A

### Sample Explanation We use $>$ to represent charging, and $\to$ to represent walking. For the first test case, a possible moving way is: $(0,0)>(2,0)\to(3,0)\to(4,0)\to(4,1)>(4,3)>(4,5)$. For the second test case, a possible moving way is: $(0,0)\to(0,1)\to(1,1)$. For the third test case, a possible moving way is: $(0,0)>(0,8)>(8,8)$. ### Constraints **Subtasks applied.** You can only gain the score of the subtask if you accepted all the tests in the subtask. | Subtask ID | $T$ | $a,b,l$ | $k$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $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$ | For all tests, it is guaranteed that $1 \leq T \leq 10^5$，$0 \leq a,b,k,l\leq 10^{9}$.