← 返回题目列表

Codeforces · 2002/F2

F2. 宫廷蓝(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。该版本不保证$$$n=m$$$,且时间限制较高。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

蓝王的法庭上,莱尔和弗拉姆正在进行一场表演赛。比赛由几轮组成。在每一轮中,Lelle 或 Flamm 获胜。

让$$$W_L$$$和$$$W_F$$$分别表示Lelle和Flamm的获胜次数。蓝王认为比赛成功当且仅当:

- 每轮结束后,$$$\gcd(W_L,W_F)\le 1$$$;
- 比赛结束时,$$$W_L\le n,W_F\le m$$$。

请注意,对于每个非负整数 $$$x$$$, $$$\gcd(0,x)=\gcd(x,0)=x$$$ 。

Lelle和Flamm可以随时决定停止比赛,最终表演得分为$$$l \cdot W_L + f \cdot W_F$$$。

请帮助Lelle和Flamm协调胜负,使表演成功,使表演总分最大化。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的唯一行包含四个整数 $$$n$$$, $$$m$$$, $$$l$$$, $$$f$$$ ($$$2\leq n\leq m \leq 2\cdot 10^7$$$, $$$1\leq l,f \leq 10^9$$$): $$$n$$$, $$$m$$$ 给出了 Lelle 和 Flamm 获胜次数的上限,$$$l$$$ 和 $$$f$$$ 决定了表演的最终分数。

不寻常的附加约束:保证对于每个测试,不存在具有相同对 $$$n$$$、$$$m$$$ 的测试用例对。

输出

对于每个测试用例,输出一个整数 - 成功表演的最高总分。

示例

输入 #1

8
3 4 2 5
4 4 1 4
6 6 2 2
7 9 2 3
8 9 9 1
2 7 1 4
5 9 1 4
5 6 6 7

输出 #1

22
17
18
37
77
30
41
59

输入 #2

2
3082823 20000000 1341 331
20000000 20000000 3 5

输出 #2

10754065643
159999991

输入 #3

1
139 1293 193 412

输出 #3

559543

注意

在第一个测试用例中,可能的性能如下:

- Flamm 获胜,$$$\gcd(0,1)=1$$$。
- Lelle 获胜,$$$\gcd(1,1)=1$$$。
- Flamm 获胜,$$$\gcd(1,2)=1$$$。
- Flamm 获胜,$$$\gcd(1,3)=1$$$。
- Flamm 获胜,$$$\gcd(1,4)=1$$$。
- Lelle 和 Flamm 同意停止比赛。

最终得分为$$$1\cdot2+4\cdot5=22$$$。