AT_abc258_f [ABC258F] Main Street

题目描述

在 $xy$ 平面上，AtCoder 王国的道路由所有整数 $n$ 的直线 $x=n$ 以及直线 $y=n$ 组成。其中，所有整数 $n$ 的直线 $x=Bn$ 以及直线 $y=Bn$ 被称为大通道。

高桥君在 $(x, y)$ 位置时，可以移动到 $(x, y-1)$、$(x, y+1)$、$(x+1, y)$ 或 $(x-1, y)$。每次移动，如果沿着大通道移动，则花费 $1$ 秒，否则花费 $K$ 秒。

请你求出高桥君从 $(S_x, S_y)$ 移动到 $(G_x, G_y)$ 的最短时间。

本题包含 $T$ 组测试数据。

输入格式

输入以如下格式从标准输入读入。

$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$

每组测试数据格式如下：

$B\ K\ S_x\ S_y\ G_x\ G_y$

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

输入输出样例 #1

输入 #1

4
3 4 2 2 4 4
5 6 2 3 2 3
1 1000000000 0 0 1000000000 1000000000
1000000000 1000000000 500000000 500000000 1000000000 1000000000

输出 #1

10
0
2000000000
500000000500000000

输入输出样例 #2

输入 #2

10
928184439 674654465 203937094 186855052 851783856 805293696
55480262 448852233 823161539 786348805 550018803 322680316
891870741 235679524 32164572 497841190 620600021 96487871
321502816 428964257 499656016 521484999 717623189 824784374
144040837 680268887 76238777 371138006 350230937 78690135
768922620 799628518 403830696 60449731 218880692 88319939
482031503 121412614 472330444 284479575 949635609 427232765
389524418 132987043 656496997 678732442 23028233 488463974
857778764 629964237 714551548 739330018 579247790 874251485
461612428 535402609 555160129 833592114 44418273 287363785

输出 #2

177606591118701316
6205925075792263
30320747646118343
84136273267803188
83764071874751489
118960470930399064
2929499649126153
16403238161749820
84995699148879437
71771264361119335

说明/提示

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq B, K \leq 10^9$
• $0 \leq S_x, S_y, G_x, G_y \leq 10^9$
• 所有输入均为整数。

样例解释 1

对于第 $1$ 组测试数据，可以从 $(2,2)$ 移动到 $(2,3)$，花费 $4$ 秒；再从 $(2,3)$ 移动到 $(4,3)$，花费 $2$ 秒；最后从 $(4,3)$ 移动到 $(4,4)$，花费 $4$ 秒。总共需要 $10$ 秒，无法更快，因此答案为 $10$。对于第 $2$ 组测试数据，起点就是 $(G_x, G_y)$，所以答案为 $0$。

由 ChatGPT 4.1 翻译