408227: GYM103059 H Pancake Scheduling

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Pancake Schedulingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Don's new breakfast chain, Donny's, is a huge success! Today, he has received orders for $$$N$$$ pancakes ($$$1 \leq N \leq 10^{12}$$$). Don has two frying pans with which to cook the pancakes: the first pan can cook one pancake in $$$A$$$ minutes, while the second pan can cook one pancake in $$$B$$$ minutes ($$$1 \leq A, B \leq 10^6$$$). As a master chef, Don can use both pans simultaneously, and it takes no time to move pancakes in and out of the frying pans. However, once a pancake starts cooking in a pan, it must stay in that pan until the pancake is finished cooking. What is the minimum amount of time, in minutes, that Don needs to cook all $$$N$$$ pancakes?

Input

There is one line of input with three integers, separated by spaces.

The first integer is N, the number of pancakes Don needs to cook ($$$1 \leq N \leq 10^{12}$$$). The second integer is $$$A$$$, the number of minutes it takes Don's first pan to cook one pancake ($$$1 \leq A \leq 10^6$$$). The third integer is $$$B$$$, the number of minutes it takes Don's second pan to cook one pancake ($$$1 \leq B \leq 10^6$$$).

Output

Output a single integer, the minimum number of minutes for Don to cook all $$$N$$$ pancakes.

ExamplesInput
5 2 3
Output
6
Input
6 2 3
Output
8
Input
3 3 9
Output
9
Note

In the first sample test case, we have a pan that cooks a pancake every 2 minutes, and a pan that cooks a pancake every three minutes. To cook 5 pancakes, we can let the first pan cook 3 pancakes in 6 minutes, and the second pan can cook 2 pancakes in 6 minutes. Since Don can use both pans at the same time, this takes 6 minutes total.

In the second sample test case, Don needs at least 8 minutes. To cook 6 pancakes, we can let the first pan cook 4 pancakes in 8 minutes, and the second pan can cook 2 pancakes in 6 minutes.

In the third sample test case, Don needs at least 9 minutes. One possible way to cook 3 pancakes is to let the first pan cook 2 pancakes in 6 minutes, and the second pan can cook 1 pancake in 9 minutes, for a total of 3 pancakes in 9 minutes.

Be sure to use 64-bit integers!

加入题单

上一题 下一题 算法标签: