There's a scientist named Brook who is interested in budding of cells. He has one container which initially contains only a single cell. Now Brook wants n number of cells in his container. So he can change the number of cells in container in 3 different ways -:

Double the number of cells present in the container.

Increase the number of cells in the container by 1.

Decrease the number of cells in the container by 1.

Now, all the above operations have different costs associated with them x,y,z respectively for above operations. Help brook in finding the minimum cost to generate n cells in the container starting from one cell Constraints 1<=n<=10^5 1<=x<=y<=z<=10^5

Output Format Output an integer denoting the minimum cost incurred to create n cells

Sample Input 5 2 1 3 Sample Output 4