PROG-T1036: Equipped

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int cost[N + 1], dp[N + 2][1 << 8];
bool tasks[N + 1][8];

int main(){

    int nItem, task;
    scanf("%d%d", &nItem, &task);
    for(int i = 1; i <= nItem; ++i){
        scanf("%d", &cost[i]);
        for(int j = 0; j < task; ++j){
            scanf("%d", &tasks[i][j]);
        }
    }
    for(int i = 1; i <= nItem + 1; ++i){
        dp[i][(1 << task) - 1] = 0;
    }
    for(int btw = 0; btw < (1 << task); ++btw){
        dp[nItem + 1][btw] = 1e9;
    }
    for(int i = nItem; i >= 1; --i){
        for(int btw = (1 << task) - 2; btw >= 0; --btw){
            int newBtw = btw;
            for(int j = 0; j < task; ++j){
                if(tasks[i][j]){
                    newBtw |= (1 << j);
                }
            }
            dp[i][btw] = min(cost[i] + dp[i + 1][newBtw], dp[i + 1][btw]);
        }
    }
    cout << dp[1][0];

    return 0;
}