← 返回题目列表

Codeforces · 2002/F1

F1. 宫廷蓝(简单版)

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

这是问题的简单版本。在这个版本中,$$$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$$$, $$$\bf{n=m}$$$):$$$n$$$、$$$m$$$ 给出了 Lelle 和 Flamm 获胜次数的上限,$$$l$$$ 和 $$$f$$$ 决定了表演的最终分数。

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

输出

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

示例

输入 #1

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

输出 #1

19
17
18
33
86
9
24
86

输入 #2

1
20000000 20000000 1341 331

输出 #2

33439999007

输入 #3

2
1984 1984 19 84
9982 9982 44 35

输出 #3

204143
788403

注意

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

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

最终得分为$$$2\cdot2+3\cdot5=19$$$。

在第三个测试用例中,可能的表现如下:

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

最终得分为$$$5\cdot2+4\cdot2=18$$$。请注意,即使 Lelle 和 Flamm 都没有赢得 $$$n$$$ 胜利,他们也可以停止比赛。