题目描述

r-906 & IA AI - Psychologic Disco

给定两个非负整数 $a, b$。你可以对 $a$ 进行任意次数、任意顺序的两种操作：

• $a \gets a + 1$。该操作的花费为 $x$；
• $a \gets a \oplus 1$，其中 $\oplus$ 表示按位异或操作。该操作的花费为 $y$。

现在要求你将 $a$ 变为 $b$。如果可以做到，输出最小花费；否则，输出 $-1$。

输入格式

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的一行包含四个整数 $a, b, x, y$（$1 \le a, b \le 100, 1 \le x, y \le 10^7$）——给定的两个整数以及两种操作各自的花费。

输出格式

对于每个测试用例，输出一个整数——将 $a$ 变为 $b$ 的最小花费。如果无法做到，输出 $-1$。

说明/提示

在第一个测试用例中，最优策略是执行三次 $a \gets a + 1$ 操作。总花费为 $1+1+1=3$。

在第二个测试用例中，最优策略是依次执行 $a \gets a + 1$、$a \gets a \oplus 1$、$a \gets a + 1$、$a \gets a \oplus 1$。总花费为 $2+1+2+1=6$。

在第五个测试用例中，可以证明无法将 $a$ 变为 $b$。

由 ChatGPT 4.1 翻译

样例

7
1 4 1 2
1 5 2 1
3 2 2 1
1 3 2 1
2 1 1 2
3 1 1 2
1 100 10000000 10000000

3
6
1
3
-1
-1
990000000