[SW Expert Academy] 1952. 수영장

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define p pair<int,int>
using namespace std;

int cost[4];
int map[12];
int ans;

void dfs(int idx, int sum){
    if( idx >= 12 ){
        ans = ans < sum ? ans : sum;
        return ;
    }
    
    if( map[idx] == 0 ){
        dfs(idx+1,sum);
        return ;
    }
    
    // 1일권
    dfs(idx+1, sum + (cost[0] * map[idx]));
    
    // 1달권
    dfs(idx+1, sum + cost[1]);
    
    // 3달권
    dfs(idx+3, sum + cost[2]);    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        for(int i=0; i<4; i++)
            cin >> cost[i];
        
        for(int i=0; i<12; i++)
            cin >> map[i];
        
        ans = cost[3];
        dfs(0,0);
        
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}