### 问题描述

慧慧目前位于原点 $0$，有一天她想前往位置 $N$ 去执行冒险任务。她是一名伟大的魔法师，计划通过转移魔法来进行移动。

假设慧慧当前的位置为 $x$ ，她有以下几种移动操作：

• 释放低级转移魔法，消耗 $A$ 点能量，转移到 $2 \times x$ 位置。
• 释放中级转移魔法，消耗 $B$ 点能量，转移到 $3 \times x$ 位置。
• 释放高级转移魔法，消耗 $C$ 点能量，转移到 $5 \times x$ 位置。
• 步行，消耗 $D$ 点能量，可转移到 $x + 1$ 或者 $x - 1$ 位置。

众所周知，慧慧是一个做事颇为严谨的人，她并不想贸然地进行移动，你能帮助她确定从原点到达位置 $N$ 最少需要消耗多少能量吗？

输入格式

第一行输入五个正整数 $N,A,B,C,D$ 表示终点的位置以及各项行动的能量消耗。

输出格式

输出一个正整数表示慧慧到达终点的最小能量消耗。

样例输入1

11 1 2 4 8

样例输出1

20

样例输入2

11 1 2 2 8

样例输出2

19

说明

• 样例 $1$：慧慧可以进行如下操作，使得最终能量消耗最小。
  • 初始状态下 $x = 0$。
  • 消耗 $8$ 点能量往后走一格，此时 $x = 1$。
  • 消耗 $1$ 点能量释放低级魔法，此时 $x = 2$。
  • 消耗 $1$ 点能量释放低级魔法，此时 $x = 4$。
  • 消耗 $2$ 点能量释放中级魔法，此时 $x = 12$。
  • 消耗 $8$ 点能量往前走一格，此时 $x = 11$。
  • 共计消耗 $20$ 点能量。
• 样例 $2$：慧慧可以进行如下操作，使得最终能量消耗最小。
  • 初始状态下 $x = 0$。
  • 消耗 $8$ 点能量往后走一格，此时 $x = 1$。
  • 消耗 $1$ 点能量释放低级魔法，此时 $x = 2$。
  • 消耗 $2$ 点能量释放高级魔法，此时 $x = 10$。
  • 消耗 $8$ 点能量往后走一格，此时 $x = 11$。
  • 共计消耗 $19$ 点能量。

评测数据规模

对于所有的评测数据，$1\le N\le 10^{18}$，$1 \le A,B,C,D \le 10^9$。