#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define gcd __gcd
#define pr(n) printf("%d ",n)
#define out(n) printf("%d\n",n)
#define inl(a) cin >> a
#define prl(a) cout << a << " "
#define outl(a) cout << a << endl
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define ck printf("continue\n")
#define all(vec) vec.begin(),vec.end()
#define asc(vec) sort(vec.begin(),vec.end())
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define N 5000001
typedef long long int ll;
class MahdiJumping {
public:
long long minDis(int, int, int, int, int);
};
long long minDis(int n, int A, int B, int a, int b)
{
ll ans=N;
ans*=N;
vector<ll> dp(n,ans);
//vi vis(n,0);
vector<bool> vis(n,false);
dp[0]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > pq;
pq.push({0,0});
pair<ll,int> xy;
int s;
while(!pq.empty() && !vis[n-1])
{
xy=pq.top();
pq.pop();
s=xy.S,ans=xy.F;
if(!vis[s])
{
vis[s]=1;
if(s+1<n && !vis[s+1] && dp[s+1]>dp[s]+a)
dp[s+1]=dp[s]+a,pq.push({dp[s+1],s+1});
ans=A,ans*=s,ans+=B;
ans%=n;
if(!vis[ans] && dp[ans]>dp[s]+b)
dp[ans]=dp[s]+b,pq.push({dp[ans],ans});
}
}
return dp[n-1];
}
int main()
{
outl(minDis(5000000, 1, 5, 1, 5000000));
}
//Powered by [KawigiEdit] 2.0!
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBNIDEwMDAwMDAwMDcKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBnY2QgX19nY2QKI2RlZmluZSBwcihuKSBwcmludGYoIiVkICIsbikKI2RlZmluZSBvdXQobikgcHJpbnRmKCIlZFxuIixuKQojZGVmaW5lIGlubChhKSBjaW4gPj4gYQojZGVmaW5lIHBybChhKSBjb3V0IDw8IGEgPDwgIiAiCiNkZWZpbmUgb3V0bChhKSBjb3V0IDw8IGEgPDwgZW5kbAojZGVmaW5lIHllcyBwcmludGYoIllFU1xuIikKI2RlZmluZSBubyBwcmludGYoIk5PXG4iKQojZGVmaW5lIGxpbiBwcmludGYoIlxuIikKI2RlZmluZSBkYmcodixpLG4pIGZvcihpPTA7aTxuO2krKylwcih2W2ldKTsgbGluCiNkZWZpbmUgY2sgcHJpbnRmKCJjb250aW51ZVxuIikKI2RlZmluZSBhbGwodmVjKSB2ZWMuYmVnaW4oKSx2ZWMuZW5kKCkKI2RlZmluZSBhc2ModmVjKSBzb3J0KHZlYy5iZWdpbigpLHZlYy5lbmQoKSkKI2RlZmluZSBsb3dlcih2LGspIGxvd2VyX2JvdW5kKHYuYmVnaW4oKSx2LmVuZCgpLGspLXYuYmVnaW4oKQojZGVmaW5lIHVwcGVyKHYsaykgdXBwZXJfYm91bmQodi5iZWdpbigpLHYuZW5kKCksayktdi5iZWdpbigpCiNkZWZpbmUgdGYobXl0dXBsZSkgZ2V0PDA+KG15dHVwbGUpCiNkZWZpbmUgdHMobXl0dXBsZSkgZ2V0PDE+KG15dHVwbGUpCiNkZWZpbmUgdHQobXl0dXBsZSkgZ2V0PDI+KG15dHVwbGUpCiNkZWZpbmUgaWkgcGFpcjxpbnQsaW50PgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdmlpIHZlY3RvcjxwYWlyPGludCxpbnQ+ID4KI2RlZmluZSB2dmkgdmVjdG9yPHZlY3RvcjxpbnQ+ID4KI2RlZmluZSB2aWlpIHZlY3RvcjxwYWlyPHBhaXI8aW50LGludD4saW50PiA+CiNkZWZpbmUgdnZpaSB2ZWN0b3I8dmVjdG9yPHBhaXI8aW50LGludD4gPiA+CiNkZWZpbmUgbHAoaSxhLGIpIGZvcihpPWE7aTxiO2krKykKI2RlZmluZSByZXAoaSxuKSBmb3IoaT0wO2k8bjtpKyspCiNkZWZpbmUgTiA1MDAwMDAxCnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCmNsYXNzIE1haGRpSnVtcGluZyB7CnB1YmxpYzoKCWxvbmcgbG9uZyBtaW5EaXMoaW50LCBpbnQsIGludCwgaW50LCBpbnQpOwp9OwoKbG9uZyBsb25nIG1pbkRpcyhpbnQgbiwgaW50IEEsIGludCBCLCBpbnQgYSwgaW50IGIpCnsKICAgIGxsIGFucz1OOwogICAgYW5zKj1OOwogICAgdmVjdG9yPGxsPiBkcChuLGFucyk7CiAgICAvL3ZpIHZpcyhuLDApOwogICAgdmVjdG9yPGJvb2w+IHZpcyhuLGZhbHNlKTsKICAgIGRwWzBdPTA7CiAgICBwcmlvcml0eV9xdWV1ZTxwYWlyPGxsLGludD4sdmVjdG9yPHBhaXI8bGwsaW50PiA+ICxncmVhdGVyPHBhaXI8bGwsaW50PiA+ID4gcHE7CiAgICBwcS5wdXNoKHswLDB9KTsKICAgIHBhaXI8bGwsaW50PiB4eTsKICAgIGludCBzOwogICAgd2hpbGUoIXBxLmVtcHR5KCkgJiYgIXZpc1tuLTFdKQogICAgewogICAgICAgIHh5PXBxLnRvcCgpOwogICAgICAgIHBxLnBvcCgpOwogICAgICAgIHM9eHkuUyxhbnM9eHkuRjsKICAgICAgICBpZighdmlzW3NdKQogICAgICAgIHsKICAgICAgICAgICAgdmlzW3NdPTE7CiAgICAgICAgICAgIGlmKHMrMTxuICYmICF2aXNbcysxXSAmJiBkcFtzKzFdPmRwW3NdK2EpCiAgICAgICAgICAgICAgICBkcFtzKzFdPWRwW3NdK2EscHEucHVzaCh7ZHBbcysxXSxzKzF9KTsKICAgICAgICAgICAgYW5zPUEsYW5zKj1zLGFucys9QjsKICAgICAgICAgICAgYW5zJT1uOwogICAgICAgICAgICBpZighdmlzW2Fuc10gJiYgZHBbYW5zXT5kcFtzXStiKQogICAgICAgICAgICAgICAgZHBbYW5zXT1kcFtzXStiLHBxLnB1c2goe2RwW2Fuc10sYW5zfSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGRwW24tMV07Cn0KCmludCBtYWluKCkKewoJb3V0bChtaW5EaXMoNTAwMDAwMCwgMSwgNSwgMSwgNTAwMDAwMCkpOwp9Ci8vUG93ZXJlZCBieSBbS2F3aWdpRWRpdF0gMi4wIQ==