Description

Xenocide最近又迷上了塔防游戏，游戏是这样的：在1张N个格子的地图里，所有格子在一条线上，每一个格子上都可以放一个塔，他可以作用到当前格子上。现在你可以建3种塔分别是 火塔，冰塔和毒塔，他们的作用分别是：

火塔：使敌人在这个格子内每秒受到f点伤害

冰塔：走出一个格子的时间加长b秒，在走出冰塔所在格子后生效，可叠加

毒塔：在之后每秒受到d点伤害，在走出毒塔所在格子后生效，可叠加

现在已知 总共有n个格子，敌人一开始走过一个格子要s秒

xenocide很想知道怎样在每个格子上建塔才能让敌人扣血最多，所以你能不能帮他计算敌人走出地图最多扣多少血

注意所有效果永久有效。

Input

有多组数据 每组输入5个正整数 n , s , f , b , d（n <=1000 ; s , f , b , d<100）

Output

问敌人走出地图最多扣多少血

Sample

Input

3 1 1 1 1
5 1 4 1 1

Output

5
36

Hint

请用long long 输出

Source: Xenocide