Last year, at the municipal stage, there was a task about employees of the business center who leave work in the evening. Now solve the problem about the employees of the business center who come to work in the morning.
The business center is an N-storey building, the floors are numbered from 1 to N from bottom to top. Each floor has exactly one employee. All employees arrive in the morning at the parking lot, which is located in the basement, one floor below the first. The business center is equipped with an elevator that can accommodate an unlimited number of people, but today the harmful elevator operator is ready to take all employees to just one floor.
Each employee has a choice: he can walk up the stairs, it will take A seconds to climb one floor. Or he can take the elevator, which will take all the employees to some floor they have chosen together. After leaving the elevator, the employee can go up to his floor (also spending A seconds to go up one floor), or go down to the desired floor down, spending B seconds to go down one floor. The elevator takes C seconds to go up one floor.
Determine the minimum time it takes for all employees to go to their floors if they make the best choice of the floor the elevator goes to and their behavior strategy (climb the stairs or ride the elevator and then walk the stairs).
The first line of the input contains the number N – number of floors in the business center. The next three lines contain the numbers A, B, C – the time it takes an employee to go up one floor, down one floor and the time it takes an elevator to go up one floor. All numbers – positive integers not exceeding 2×10
9 , while A ≥ B, A &g; C. The program should output a single integer – the minimum time for all employees to reach their floor.
| Input |
Output |
Note |
6
20
10
5 |
45 |
The building has 6 floors. An employee goes up one floor in 20 seconds, goes down in 10 seconds. The elevator goes up one floor in 5 seconds. To get everyone to their seats faster, the elevator goes to the 5th floor in 25 seconds. An employee who works on the 6th floor gets off the elevator and goes up in 20 seconds, for a total journey of 45 seconds. An employee working on the 3rd floor takes the elevator and goes down 2 floors, this also takes 45 seconds. Employees from the 4th and 5th floors also ride the elevator, their journey will be faster than 45 seconds. On the 1st and 2nd floors, employees walk up the stairs in 20 and 40 seconds, respectively. In total, all employees get to their floors in no more than 45 seconds. |