Это простая версия задачи. В этой версии \(n=m\) и ограничение по времени меньше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Во дворе Синего короля Лелль и Фламм устраивают матч. Матч состоит из нескольких раундов. В каждом раунде побеждает либо Лелль, либо Фламм.
Пусть \(W_L\) и \(W_F\) обозначают количество побед Лелли и Фламма, соответственно. Синий король считает матч успешным тогда и только тогда, когда:
- после каждого раунда, \(\gcd(W_L,W_F)\le 1\);
- в конце матча \(W_L\le n, W_F\le m\).
Обратите внимание, что \(\gcd(0,x)=\gcd(x,0)=x\) для каждого целого неотрицательного числа \(x\).
Лелль и Фламм могут прекратить матч, когда захотят, а итоговый счет матча будет следующим: \(l \cdot W_L + f \cdot W_F\).
Пожалуйста, помогите Лелле и Фламму скоординировать свои победы и поражения так, чтобы матч был успешным, а итоговый счет за матч был максимальным.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальный итоговый счет успешного матча.
Примечание
В первом наборе входных данных возможный матч выглядит так:
- Фламм выигрывает, \(\gcd(0,1)=1\).
- Лелль выигрывает, \(\gcd(1,1)=1\).
- Фламм выигрывает, \(\gcd(1,2)=1\).
- Фламм выигрывает, \(\gcd(1,3)=1\).
- Лелль выигрывает, \(\gcd(2,3)=1\).
- Лелль и Фламм соглашаются прекратить матч.
Итоговый счет: \(2\cdot2+3\cdot5=19\).
В четвертом наборе входных данных возможный матч выглядит так:
- Фламм выигрывает, \(\gcd(0,1)=1\).
- Лелль выигрывает, \(\gcd(1,1)=1\).
- Лелль выигрывает, \(\gcd(2,1)=1\).
- Лелль выигрывает, \(\gcd(3,1)=1\).
- Лелль выигрывает, \(\gcd(4,1)=1\).
- Лелль выигрывает, \(\gcd(5,1)=1\).
- Фламм выигрывает, \(\gcd(5,2)=1\).
- Фламм выигрывает, \(\gcd(5,3)=1\).
- Фламм выигрывает, \(\gcd(5,4)=1\).
- Лелль и Фламм соглашаются прекратить матч.
Итоговый счет: \(5\cdot2+4\cdot2=18\). Обратите внимание, что Лелль и Фламм могут прекратить матч, даже если ни у одного из них нет \(n\) выигрышей.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
19
17
18
33
86
9
24
86
|
|
2
|
1
20000000 20000000 1341 331
|
33439999007
|
|
3
|
2
1984 1984 19 84
9982 9982 44 35
|
204143
788403
|