#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>

const unsigned int MAX_ITER = 5;
const double EPS = 1e-8;

unsigned short randomInRange(unsigned short lb, unsigned short ub)
{
    return lb + std::rand() % (ub - lb + 1);
}

bool isStopCriteriaReached(double& prev, double& curr, double eps)
{
    return fabs(prev - curr) < eps;
}

void getL(
    double* lambda,
    unsigned int* p, unsigned short** w,
    unsigned short n, unsigned short m,
    unsigned short gIndx,
    double* l
) {
    for (unsigned short i = 0; i < n; ++i) {
        l[i] = p[i];

        for (unsigned short j = 0; j < m; ++j) {
            if (j != gIndx) {
                l[i] -= w[i][j] * lambda[j];
            }
        }
    }
}

double getD(
    unsigned short n, unsigned short m,
    double* l, unsigned short* x,
    unsigned short* c, double* lambda,
    unsigned short gIndx
) {
    double res = 0;
    for (unsigned short i = 0; i < n; ++i) {
        res += l[i] * x[i];
    }
    for (unsigned short j = 0; j < m; ++j) {
        if (j != gIndx) {
            res += c[j] * lambda[j];
        }
    }
    return res;
}

void getSubgrad(
    unsigned short n, unsigned short m,
    unsigned short** w, unsigned short gIndx,
    unsigned short* c,
    unsigned short* x,
    short* subgrad
) {
    for (unsigned short j = 0; j < m; ++j) {
        if (j != gIndx) {
            subgrad[j] = c[j];
            for (unsigned short i = 0; i < n; ++i) {
                subgrad[j] -= w[i][j] * x[i];
            }
        }
    }
}

double getSubgradNorm(
    unsigned short m, unsigned short gIndx,
    short* subgrad
) {
    double res = 0;
    for (unsigned short j = 0; j < m; ++j) {
        if (j != gIndx) {
            res += subgrad[j] * subgrad[j];
        }
    }

    return sqrt(res);
}

void getNextLambda(
    unsigned short m, unsigned short gIndx,
    double* lambda, short* subgrad,
    double step
) {
    double subgradNorm = getSubgradNorm(m, gIndx, subgrad);

    for (unsigned short j = 0; j < m; ++j) {
        if (j != gIndx) {
            lambda[j] -= step * subgrad[j] / (subgradNorm + EPS);
            lambda[j] = std::max(0., lambda[j]);
        }
    }
}

struct Node
{
    short v, prev;
    int w;
    double p;
};

Node createNode(short v, short prev, int w, double p)
{
    Node res;
    res.v = v;
    res.prev = prev;
    res.w = w;
    res.p = p;
    return res;
}

void solve1DimBackpack(
    unsigned short n, unsigned short c,
    double* p, unsigned short* w,
    double& ans, unsigned short* x
) {
    std::vector<Node>* D = new std::vector<Node>[n + 1]; // 1-indexation per first dim
    D[0].push_back(createNode(-1, -1, 0, 0));

    for (short i = 0; i < n; ++i) { // iterating items
        short it0 = 0;
        short it1 = 0;

        while (it0 < D[i].size() && it1 < D[i].size()) {
            // both tuples are not empty
            Node node0 = createNode(0, it0, D[i][it0].w, D[i][it0].p);

            if (D[i][it1].w + w[i] > c) {
                ++it1; // skip 1, too tight borders
                continue;
            }
            Node node1 = createNode(1, it1, D[i][it1].w + w[i], D[i][it1].p + p[i]);

            if ( // dominated, 0 > 1
                node0.w <= node1.w &&
                node0.p >= node1.p
                ) {
                ++it1; // just skip 1
            }
            else if ( // dominated, 1 > 0
                node1.w <= node0.w &&
                node1.p >= node0.p
                ) {
                ++it0; // just skip 0
            }
            else if ( // ordinary, 0 > 1
                node0.w <= node1.w
                ) {
                D[i + 1].push_back(node0);
                ++it0; // next 0
            }
            else if ( // ordinary, 1 > 0
                node1.w <= node0.w
                ) {
                D[i + 1].push_back(node1);
                ++it1; // next 1
            }
        }

        // fill the rest
        while (it0 < D[i].size()) {
            Node node0 = createNode(0, it0, D[i][it0].w, D[i][it0].p);
            if ( // ignore dominated
                !D[i + 1].empty() &&
                D[i + 1].back().w <= node0.w &&
                D[i + 1].back().p >= node0.p
                ) {
                ++it0; // just skip 1
            }
            else {
                D[i + 1].push_back(node0);
                ++it0;
            }
        }

        while (it1 < D[i].size()) {
            if (D[i][it1].w + w[i] > c) {
                ++it1; // skip 1, too tight borders
                continue;
            }
            Node node1 = createNode(1, it1, D[i][it1].w + w[i], D[i][it1].p + p[i]);

            if ( // ignore dominated
                !D[i + 1].empty() &&
                D[i + 1].back().w <= node1.w &&
                D[i + 1].back().p >= node1.p
                ) {
                ++it1; // just skip 1
            }
            else {
                D[i + 1].push_back(node1);
                ++it1;
            }
        }
    }

    // answer backtracking
    int itN = n;
    int itL = D[itN].size() - 1;

    std::vector<short> path;

    while (D[itN][itL].prev != -1) {
        if (D[itN][itL].v == 1) {
            path.push_back(itN - 1); // cast 1-indexation to 0
        }
        itL = D[itN][itL].prev;
        --itN;
    }

    ans = D[n].back().p;

    for (short i = 0; i < path.size(); ++i) {
        x[path[i]] = 1;
    }

    delete[] D;
}

double getLagrangianEstimation(
    unsigned short n, unsigned short m,
    unsigned short* c, unsigned int* p,
    unsigned short** w
) {
    unsigned int currIter = 1;
    unsigned short gIndx = randomInRange(0, m - 1); //selected subject index
    double* currLambda = new double[m];
    double prevD = -1e9;
    double D;

    for (unsigned short i = 0; i < m; ++i) {
        currLambda[i] = 1;
    }

    while (currIter <= MAX_ITER) {
        // implementing dual problem
        double* l = new double[n];
        getL(currLambda, p, w, n, m, gIndx, l);

        unsigned short* x = new unsigned short[n];
        for (unsigned short i = 0; i < n; ++i) {
            x[i] = 0;
        }

        // getting x*(lambda), D(lambda)
        unsigned short* wPer1Dim = new unsigned short[n];
        for (unsigned short i = 0; i < n; ++i) {
            wPer1Dim[i] = w[i][gIndx];
        }

        double currAns = 0;
        solve1DimBackpack(n, c[gIndx], l, wPer1Dim, currAns, x);
        delete[] wPer1Dim;

        D = getD(n, m, l, x, c, currLambda, gIndx);

        // checking stopping criteria
        if (isStopCriteriaReached(D, prevD, EPS)) {
            delete[] l, x;
            break;
        }

        // moving to next step
        if (currIter + 1 < MAX_ITER) {
            double step = 1. / (currIter + 1);
            short* subgrad = new short[m];
            getSubgrad(n, m, w, gIndx, c, x, subgrad);
            getNextLambda(m, gIndx, currLambda, subgrad, step);

            prevD = D;

            delete[] subgrad;
        }

        delete[] l, x;
        ++currIter;
    }

    delete[] currLambda;

    // output
    return D;
}

void branchAndBoundMethod(
    unsigned short currIt,
    unsigned short n, unsigned short m,
    unsigned short* c, unsigned int* p,
    unsigned short** w,
    unsigned short* x,
    unsigned short* recordX,
    unsigned int& recordValue,
    unsigned int currObjectiveValue
) {
    // recursion stop criteria
    if (currIt >= n) {
        if (currObjectiveValue > recordValue) {
            for (int i = 0; i < n; ++i) {
                recordX[i] = x[i];
            }
            recordValue = currObjectiveValue;
        }
        return;
    }

    // estimate the 1-subtree
    bool isValidSubtree = true;
    unsigned short* unfixedC = new unsigned short[m];
    for (unsigned short j = 0; j < m; ++j) {
        unfixedC[j] = c[j] - w[currIt][j];
        if (w[currIt][j] > c[j]) {
            isValidSubtree = false;
        }
    }

    unsigned int* unfixedP = new unsigned int[n - currIt - 1];
    for (unsigned short i = 0; i < n - currIt - 1; ++i) {
        unfixedP[i] = p[i + currIt + 1];
    }

    unsigned short** unfixedW = new unsigned short* [n - currIt - 1];
    for (unsigned short i = 0; i < n - currIt - 1; ++i) {
        unfixedW[i] = new unsigned short[m];
        for (unsigned short j = 0; j < m; ++j) {
            unfixedW[i][j] = w[i + currIt + 1][j];
        }
    }

    double D = 0;
    if (isValidSubtree) {
        D = getLagrangianEstimation(
            n - currIt - 1, m,
            unfixedC, unfixedP, unfixedW
        );
    }

    // 1-branching attempt
    x[currIt] = 1;
    if (isValidSubtree && currObjectiveValue + p[currIt] + D > recordValue) {
        for (unsigned short j = 0; j < m; ++j) {
            c[j] = c[j] - w[currIt][j];
        }
        branchAndBoundMethod(
            currIt + 1,
            n, m,
            c, p, w,
            x, recordX,
            recordValue,
            currObjectiveValue + p[currIt]
        );
        for (unsigned short j = 0; j < m; ++j) {
            c[j] = c[j] + w[currIt][j];
        }
    }

    // estimate the 0-subtree
    for (unsigned short j = 0; j < m; ++j) {
        unfixedC[j] = c[j];
    }

    D = getLagrangianEstimation(
        n - currIt - 1, m,
        unfixedC, unfixedP, unfixedW
    );

    // 0-branching attempt
    x[currIt] = 0;
    if (currObjectiveValue + D > recordValue) {
        branchAndBoundMethod(
            currIt + 1,
            n, m,
            c, p, w,
            x, recordX,
            recordValue,
            currObjectiveValue
        );
    }

    delete[] unfixedC, unfixedP;
    for (unsigned short i = 0; i < n - currIt - 1; ++i) {
        delete[] unfixedW[i];
    }

    return;
}

int main()
{
    // input
    unsigned short n, m;
    scanf("%hu %hu", &n, &m);

    unsigned int* p = new unsigned int[n];
    for (unsigned short i = 0; i < n; ++i) {
        scanf("%u", &p[i]);
    }

    unsigned short* c = new unsigned short[m];
    for (unsigned short i = 0; i < m; ++i) {
        scanf("%hu", &c[i]);
    }

    unsigned short** w = new unsigned short* [n];
    for (unsigned short i = 0; i < n; ++i) {
        w[i] = new unsigned short[m];
    }
    for (unsigned short j = 0; j < m; ++j) {
        for (unsigned short i = 0; i < n; ++i) {
            scanf("%hu", &w[i][j]);
        }
    }

    // algo
    unsigned short* x = new unsigned short[n];
    unsigned short* ans = new unsigned short[n];
    unsigned int ansValue = 0;
    unsigned int currObjectiveValue = 0;

    branchAndBoundMethod(
        0,
        n, m,
        c, p, w,
        x, ans,
        ansValue,
        currObjectiveValue
    );

    printf("%d\n", ansValue);
    for (unsigned short i = 0; i < n; ++i) {
        printf("%d\n", ans[i]);
    }

    // memory clean
    delete[] c, p, x, ans;
    for (unsigned short i = 0; i < n; ++i) {
        delete[] w[i];
    }

    return 0;
}