#include using namespace std; #define INF 1234567890 #define ll long long int N, A, B, C; ll dist[200001][2]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin >> N >> A >> B >> C; memset(dist, 0x3f, sizeof(dist)); priority_queue, vector >, greater > > pq; pq.push({0, N, 0}), dist[N][0] = 0; // must be nonempty!! while(!pq.empty()) { auto [d,i,j] = pq.top(); pq.pop(); if (dist[i][j] < d) continue; // case 1. add 1 ll nd = d + A + (j==0?B:0); int ni = (i+1)%N; int nj = 1; if (dist[ni][nj] > nd) pq.push({nd, ni, nj}), dist[ni][nj] = nd; // case 2. mul 2 if (d == 0) continue; nd = d + C; ni = (i*2)%N; nj = 0; if (dist[ni][nj] > nd) pq.push({nd, ni, nj}), dist[ni][nj] = nd; } for(int i=0; i