← 返回题目列表

Codeforces · 2119/A

A. 添加或异或

中文机器翻译题面 查看原题
r-906 & IA AI - 心理迪斯科

给你两个非负整数$$$a, b$$$。您可以以任意顺序对 $$$a$$$ 执行任意次数的两种类型的操作:

  • $$$a \得到 + 1$$$。此操作的成本为$$$x$$$;
  • $$$a \gets a \oplus 1$$$,其中 $$$\oplus$$$ 表示按位异或运算。此操作的成本为 $$$y$$$。

现在要求您做出 $$$a = b$$$。如果可以,输出最小成本;否则,请报告。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

示例

输入
复制

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

注意

在第一个测试用例中,最佳策略是应用 $$$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$$$。