#include <cstdio>
#include <iostream>
#include <cmath>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <algorithm>
#include <functional>
#include <fstream>
#include <numeric>
#include <string>
#include <valarray>
#include <bitset>
using namespace std;

const int INF = 1000 * 1000 * 1000;

int *_distance;

struct MinCostFlowCmp{
  bool operator () (int a,int b){

    if (_distance[a] != _distance[b])
      return(_distance[a] < _distance[b]);

    return(a < b);
  }
};

class MinCostFlow{
public:
    int n;
    bool init;
    vector<vector<int> > next,prev;

    vector<int> c,f,cost,potential,l,r;

    int *distance;
    int _cost(int s){
        return(cost[s]+potential[r[s]]-potential[l[s]]);
    }


  MinCostFlow(int n){
    this->n=n;

    init=false;
    next.clear();
    prev.clear();

    c.clear();
    f.clear();
    cost.clear();

    l.clear();
    r.clear();
    next.resize(n+1);

    prev.resize(n+1);
    potential.resize(n+1);

    distance=new int[n+1];
  }
  void push_back(int left,int right,int C,int Cost){

    if (C == 0)
      return;
    c.push_back(C);

    f.push_back(0);
    cost.push_back(Cost);
    next[left].push_back(c.size()-1);

    prev[right].push_back(c.size()-1);
    l.push_back(left);

    r.push_back(right);
  }
  int minCostFlow(int start,int end,int Max){

    if (!init){
      fill(distance+1,distance+n+1,INF);

      distance[start]=0;
      for (int count=1;count<=n;count++)

	for (int i=0;i<l.size();i++)

	  distance[r[i]]=min(distance[r[i]],distance[l[i]]+cost[i]);

      init=true;
    }
    int ans=0;
    while (Max){

      vector<bool> mark(n+1);
      for (int i=0;i<potential.size();i++)

	potential[i]-=distance[i];
      fill(distance+1,distance+n+1,INF);

      distance[start]=0;
      _distance=distance;
      set<int,MinCostFlowCmp> Set;

      for (int i=1;i<=n;i++) Set.insert(i);

      vector<int> last(n+1);
      vector<bool> is_r(n+1);

      while (Set.size()){
	int x=*Set.begin();

	Set.erase(x);
	if (distance[x] == INF) break;

	for (int i=0;i<next[x].size();i++)

	  if (c[next[x][i]] > f[next[x][i]])

	    if (distance[r[next[x][i]]] > distance[x]+_cost(next[x][i])){

	      Set.erase(r[next[x][i]]);
	      distance[r[next[x][i]]] = distance[x]+_cost(next[x][i]);

	      last[r[next[x][i]]] = next[x][i];

	      is_r[r[next[x][i]]] = true;
	      Set.insert(r[next[x][i]]);
	    }

	for (int i=0;i<prev[x].size();i++)

	  if (f[prev[x][i]])
	    if (distance[l[prev[x][i]]] > distance[x]-_cost(prev[x][i])){

	      Set.erase(l[prev[x][i]]);
	      distance[l[prev[x][i]]] = distance[x]-_cost(prev[x][i]);

	      last[l[prev[x][i]]] = prev[x][i];

	      is_r[l[prev[x][i]]] = false;
	      Set.insert(l[prev[x][i]]);
	    }
      }

      if (distance[end] == INF)
	break;
      vector<int> edges,zarib;

      int temp=end;
      while (temp != start){

	edges.push_back(last[temp]);
	if (is_r[temp])

	  zarib.push_back(1);
	else
	  zarib.push_back(-1);

	if (is_r[temp])
	  temp=l[last[temp]];

	else
	  temp=r[last[temp]];
      }
      int Min=Max;

      for (int i=0;i<edges.size();i++)

	if (zarib[i] == 1)
	  Min=min(Min,c[edges[i]]-f[edges[i]]);

	else
	  Min=min(Min,f[edges[i]]);

      Max-=Min;
      for (int i=0;i<edges.size();i++){

	ans+=cost[edges[i]]*zarib[i]*Min;
	f[edges[i]]+=zarib[i]*Min;
      }
    }

    return(ans);
  }
  int minCostFlow(int start,int end){

    return(minCostFlow(start,end,INF));
  }
};

const int MaxN = 30;
const int MaxM = 100;

struct Graph{
    vector<int> adjX[MaxM];
    vector<int> adjY[MaxN];
    int matchY[MaxN];
    int matchX[MaxM];
    Graph(){
        for(int i = 0 ;i < MaxN;i++){
            matchY[i] = 0;
            adjY[i].clear();
        }
        for(int i = 0;i < MaxM;i++){
            adjX[i].clear();
            matchX[i] = 0;
        }
    }
};

int n, m;
int v[MaxN][MaxM];
int mms[MaxN];
int allocation[MaxM];
vector<int> allocatedItems[MaxN];
bool satisfied[MaxN];
bool markXDFS[MaxM];
bool markYDFS[MaxN];
bool mark2XDFS[MaxM];
bool mark2YDFS[MaxN];
int Pair[MaxM];
int realPairValue[MaxN][MaxM];

void readInput(){
    cout << "Enter the number of agents: ";
    cin >> n;
    cout << "Enter the number of items: ";
    cin >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            cout << "Enter the value of item " << j << " for agent " << i << " ";
            cin >> v[i][j];
        }
    for(int i = 1;i <= n;i++){
        cout << "Enter the mms of agent " << i << " ";
        cin >> mms[i];
    }
}

void allocateVeryHeavyItems(){
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++)
            if(allocation[j] == 0 && v[i][j] * 4 >= 3 * mms[i]){
                allocation[j] = i;
                allocatedItems[i].push_back(j);
                satisfied[i] = true;
                break;
            }
    }
}

void allocateVeryHeavyPairs(){
    for(int i = 1;i <= n;i++){
        if(satisfied[i])
            continue;
        for(int j = 1;j <= m;j++){
            bool flg = false;
            for(int k = j + 1;k <= m;k++)
                if(allocation[j] == 0 && allocation[k] == 0 && (v[i][j] + v[i][k]) * 4 >= 3 * mms[i]){
                    allocation[j] = i;
                    allocation[k] = i;
                    allocatedItems[i].push_back(j);
                    allocatedItems[i].push_back(k);
                    satisfied[i] = true;
                    flg = true;
                    break;
                }
            if(flg)
                break;
        }
    }
}

Graph MCMWM1(){
    Graph g;
    int cnt = 0;
    int verV[MaxN + MaxM + MaxN * MaxM], verU[MaxN + MaxM + MaxN * MaxM];
    int source = m + n + 1;
    int sink = m + n + 2;
    MinCostFlow mcf(m + n + 2);
    for(int i = 1;i <= n;i++){
        if(satisfied[i])
            continue;
        verV[cnt] = source; verU[cnt++] = i;
        mcf.push_back(source, i, 1, 0);
        for(int j = 1;j <= m;j++){
            if(allocation[j] || 2 * v[i][j] < mms[i])
                continue;
            g.adjX[j].push_back(i);
            g.adjY[i].push_back(j);
            verV[cnt] = i; verU[cnt++] = j;
            mcf.push_back(i, n + j, 1, (-1) * v[i][j]);
        }
    }
    for(int i = 1;i <= m;i++)
        if(allocation[i] == 0)
            mcf.push_back(n + i, sink, 1, 0);
    mcf.minCostFlow(source, sink);
    for(int i = 0; i < cnt;i++)
        if(verV[i] != source && mcf.f[i] == 1){
            g.matchY[verV[i]] = verU[i];
            g.matchX[verU[i]] = verV[i];
        }
    return g;
}

void DFS(Graph g, int agent){
    markYDFS[agent] = true;
    for(int i = 0;i < g.adjY[agent].size();i++){
        int item = g.adjY[agent][i];
        if(markXDFS[item])
            continue;
        markXDFS[item] = true;
        DFS(g, g.matchX[item]);
    }
}

Graph buildC1(){
    Graph g = MCMWM1();
    for(int i = 1;i <= n;i++)
        if(!markYDFS[i] && g.matchY[i] == 0)
            DFS(g, i);
    for(int i = 1;i <= n;i++)
        if(!markYDFS[i] && g.matchY[i] != 0){
            int item = g.matchY[i];
            allocation[item] = i;
            allocatedItems[i].push_back(item);
        }
    return g;
}

Graph matchingRefineC1(Graph g1){
    Graph g;
    int cnt = 0;
    int verV[MaxN + MaxM + MaxN * MaxM], verU[MaxN + MaxM + MaxN * MaxM];
    int source = m + n + 1;
    int sink = m + n + 2;
    MinCostFlow mcf(m + n + 2);
    for(int i = 1;i <= n;i++){
        if(satisfied[i] || allocatedItems[i].size() == 0)
            continue;
        int heavyItem = allocatedItems[i][0];
        verV[cnt] = source; verU[cnt++] = i;
        mcf.push_back(source, i, 1, 0);
        for(int j = 1;j <= m;j++){
            if(allocation[j] || 4 * (v[i][heavyItem] + v[i][j]) < 3 * mms[i])
                continue;
            g.adjX[j].push_back(i);
            g.adjY[i].push_back(j);
            verV[cnt] = i; verU[cnt++] = j;
            mcf.push_back(i, n + j, 1, 0);
        }
    }
    for(int i = 1;i <= m;i++)
        if(allocation[i] == 0)
            mcf.push_back(n + i, sink, 1, 0);
    mcf.minCostFlow(source, sink);
    for(int i = 0; i < cnt;i++)
        if(verV[i] != source && mcf.f[i] == 1){
            g.matchY[verV[i]] = verU[i];
            g.matchX[verU[i]] = verV[i];
        }
    return g;
}

Graph refineC1(Graph g1){
    Graph g = matchingRefineC1(g1);
    for(int i = 1;i <= n;i++)
        if(g.matchY[i]){
            int item = g.matchY[i];
            allocation[item] = i;
            satisfied[i] = true;
            allocatedItems[i].push_back(item);
        }
    return g;
}

set<int> findLightItems(Graph g1){
    set<int> light;
    light.clear();
    for(int i = 1;i <= m;i++){
        if(!allocation[i] && g1.adjX[i].size() == 0)
            light.insert(i);
    }
    return light;
}

Graph addPairs(Graph g1){
    set<int> light = findLightItems(g1);
    while(true){
        bool flg = false;
        std::set<int>::iterator it1, it2;
        for (it1 = light.begin(); it1 != light.end(); ++it1){
            for(it2 = light.begin();it2 != light.end(); ++it2){
                int item1 = *it1;
                int item2 = *it2;
                if(item1 >= item2)
                    continue;
                for(int i = 1;i <= n;i++){
                    if(!markYDFS[i])
                        continue;
                    if(2 * (v[i][item1] + v[i][item2]) >= mms[i]){
                        if(!flg){
                            flg = true;
                            for(int j = 1;j <= n;j++){
                                Pair[item1] = item2;
                                realPairValue[j][item1] = v[j][item1];
                                realPairValue[j][item2] = v[j][item2];
                                v[j][item1] += v[j][item2];
                                v[j][item2] = 0;
                            }
                        }
                        g1.adjX[item1].push_back(i);
                        g1.adjY[i].push_back(item1);
                    }
                }
                if(flg){
                    light.erase(item1);
                    light.erase(item2);
                    break;
                }
            }
            if(flg)
                break;
        }
        if(!flg)
            break;
    }
    return g1;
}

Graph MCMWM2(Graph g){
    int cnt = 0;
    int verV[MaxN + MaxM + MaxN * MaxM], verU[MaxN + MaxM + MaxN * MaxM];
    int source = m + n + 1;
    int sink = m + n + 2;
    MinCostFlow mcf(m + n + 2);
    for(int i = 1;i <= n;i++){
        if(satisfied[i] || !markYDFS[i])
            continue;
        verV[cnt] = source; verU[cnt++] = i;
        mcf.push_back(source, i, 1, 0);
        for(int j = 0;j < g.adjY[i].size();j++){
            int item = g.adjY[i][j];
            verV[cnt] = i; verU[cnt++] = item;
            mcf.push_back(i, n + item, 1, (-1) * v[i][item]);
        }
    }
    for(int i = 1;i <= m;i++)
        if(allocation[i] == 0)
            mcf.push_back(n + i, sink, 1, 0);
    mcf.minCostFlow(source, sink);
    for(int i = 0; i < cnt;i++)
        if(verV[i] != source && mcf.f[i] == 1){
            g.matchY[verV[i]] = verU[i];
            g.matchX[verU[i]] = verV[i];
        }
    return g;
}

void DFS2(Graph g, int agent){
    mark2YDFS[agent] = true;
    for(int i = 0;i < g.adjY[agent].size();i++){
        int item = g.adjY[agent][i];
        if(markXDFS[item])
            continue;
        mark2XDFS[item] = true;
        DFS2(g, g.matchX[item]);
    }
}

void freePairs(){
    for(int i = 1;i <= m; i++){
        if(allocation[i] || Pair[i] == 0)
            continue;
        int item1 = i;
        int item2 = Pair[item1];
        Pair[item1] = Pair[item2] = 0;
        for(int j = 1;j <= n;j++){
            v[j][item1] = realPairValue[j][item1];
            v[j][item2] = realPairValue[j][item2];
        }
    }
}

Graph buildC2C3(Graph g1){
    g1 = addPairs(g1);
    Graph g3 = g1;
    for(int i = 1;i <= n;i++)
        g3.matchY[i] = 0;
    for(int i = 1;i <= m;i++)
        g3.matchX[i] = 0;
    g3 = MCMWM2(g3);
    for(int i = 1;i <= n;i++)
        if(markYDFS[i] && !mark2YDFS[i] && g3.matchY[i] == 0)
            DFS2(g3, i);
    for(int i = 1;i <= n;i++)
        if(markYDFS[i] && g3.matchY[i] != 0){
            int item = g3.matchY[i];
            allocation[item] = i;
            allocatedItems[i].push_back(item);
            if(Pair[item]){
                allocation[Pair[item]] = i;
                allocatedItems[i].push_back(Pair[item]);
            }
        }
    freePairs();
    return g3;
}

int setValue(vector<int> S, int agent){
    int sum = 0;
    for(int i = 0;i < S.size();i++)
        sum += v[agent][S[i]];
    return sum;
}

int setValue2(vector<int> S1, vector<int> S2, int agent){
    int sum = 0;
    for(int i = 0;i < S1.size();i++)
        sum += v[agent][S1[i]];
    for(int i = 0;i < S2.size();i++)
        sum += v[agent][S2[i]];
    return sum;
}

vector<int> findTopologicalOrder(vector<int> TP){
    while(true){
        bool flg = false;
        for(int i = 0;i < TP.size();i++){
            for(int j = i + 1;j < TP.size();j++){
                int agent1 = TP[i];
                int agent2 = TP[j];
                if(setValue(allocatedItems[agent1], agent2) <= setValue(allocatedItems[agent2], agent2))
                    continue;
                swap(TP[i], TP[j]);
                flg = true;
                break;
            }
            if(flg)
                break;
        }
        if(!flg)
            break;
    }
    return TP;
}

vector<int> findTPC1(){
    vector<int> TP;
    TP.clear();
    for(int i = 1;i <= n;i++)
        if(!satisfied[i] && !markYDFS[i])
            TP.push_back(i);
    return TP;
}

vector<int> findTPC2(){
    vector<int> TP;
    TP.clear();
    for(int i = 1;i <= n;i++)
        if(!satisfied[i] && markYDFS[i] && !mark2YDFS[i])
            TP.push_back(i);
    return TP;
}

vector<int> findTPC3s(Graph g){
    vector<int> TP;
    TP.clear();
    for(int i = 1;i <= n;i++){
        if(satisfied[i] || !markYDFS[i] || !mark2YDFS[i])
            continue;
        if(g.matchY[i])
            TP.push_back(i);
    }
    return TP;
}

vector<int> findTPC3b(Graph g){
    vector<int> TP;
    TP.clear();
    for(int i = 1;i <= n;i++){
        if(satisfied[i] || !markYDFS[i] || !mark2YDFS[i] || g.matchY[i])
            continue;
        if(g.adjY[i].size())
            TP.push_back(i);
    }
    return TP;
}

vector<int> findTPC3f(Graph g){
    vector<int> TP;
    TP.clear();
    for(int i = 1;i <= n;i++){
        if(satisfied[i] || !markYDFS[i] || !mark2YDFS[i] || g.matchY[i] || g.adjY[i].size())
            continue;
        TP.push_back(i);
    }
    return TP;
}

void refineC2C3(){
    vector<int> TPOrder = findTPC2();
    TPOrder = findTopologicalOrder(TPOrder);
    for(int i = 0;i < TPOrder.size();i++){
        int agent = TPOrder[i];
        int item = allocatedItems[agent][0];
        for(int j = 1;j <= m;j++){
            if(allocation[j])
                continue;
            if(4 * (v[agent][item] + v[agent][j]) >= 3 * mms[agent]){
                allocation[j] = agent;
                allocatedItems[agent].push_back(j);
                if(Pair[j]){
                    allocation[Pair[j]] = agent;
                    allocatedItems[agent].push_back(Pair[j]);
                }
                satisfied[agent] = true;
                break;
            }
        }
    }
}

vector<int> removeVector(vector<int> v, int x){
    std::vector<int>::iterator newEnd = std::remove(v.begin(), v.end(), x);
    v.erase(newEnd, v.end());
    return v;
}

vector<int> addVector(vector<int> v, int x){
    vector<int> res;
    res.clear();
    bool flg = false;
    for(int i = 0;i < v.size();i++){
        if(v[i] > x && !flg){
            res.push_back(x);
            flg = true;
        }
        res.push_back(v[i]);
    }
    if(!flg)
        res.push_back(x);
    return res;
}

void allocateBagf(vector<int> S, int agent, vector<int> *TPC3f, vector<int> *TPC3s, vector<int> *TPC3b){
    for(int i = 0;i < S.size();i++){
        int item = S[i];
        allocatedItems[agent].push_back(item);
        allocation[item] = agent;
    }
    (*TPC3f) = removeVector(*TPC3f, agent);
    (*TPC3s).push_back(agent);
    (*TPC3s) = findTopologicalOrder(*TPC3s);
    for(int i = 0;i < (*TPC3f).size();i++){
        int agent2 = (*TPC3f)[i];
        if(2 * setValue(S, agent2) >= mms[agent2]){
            (*TPC3f) = removeVector(*TPC3f, agent2);
            (*TPC3b) = addVector(*TPC3b, agent2);
        }
    }
}

void allocateBagb(vector<int> S, int agent1, int agent2, vector<int> *TPC3f, vector<int> *TPC3s, vector<int> *TPC3b){
    for(int i = 0;i < S.size();i++){
        int item = S[i];
        allocatedItems[agent1].push_back(item);
        allocation[item] = agent1;
    }
    for(int i = 0;i < allocatedItems[agent2].size();i++){
        int item = allocatedItems[agent2][i];
        allocatedItems[agent1].push_back(item);
        allocation[item] = agent1;
    }
    (*TPC3b) = removeVector(*TPC3b, agent1);
    satisfied[agent1] = true;
    allocatedItems[agent2].clear();
    (*TPC3s) = removeVector(*TPC3s, agent2);
    bool flg = false;
    for(int i = 0;i < (*TPC3s).size();i++){
        int agent3 = (*TPC3s)[i];
        if(2 * setValue(allocatedItems[agent3], agent2) >= mms[agent2]){
            flg = true;
            break;
        }
    }
    if(flg)
        (*TPC3b) = addVector(*TPC3b, agent2);
    else
        (*TPC3f) = addVector(*TPC3f, agent2);
}

void allocateBags(int agent, vector<int> *TPC3s){
    (*TPC3s) = removeVector(*TPC3s, agent);
}

void allocateBag1(int agent, vector<int> *TPC1){
    (*TPC1) = removeVector(*TPC1, agent);
}

void allocateBag2(int agent, vector<int> *TPC2){
    (*TPC2) = removeVector(*TPC2, agent);
}

void allocateBag(vector<int> S, int agent){
    satisfied[agent] = true;
    for(int i = 0;i < S.size();i++){
        int item = S[i];
        allocatedItems[agent].push_back(item);
        allocation[item] = agent;
    }
}

bool feasiblityCheck(vector<int> S, vector<int> *TPC1, vector<int> *TPC2, vector<int> *TPC3s, vector<int> *TPC3b, vector<int> *TPC3f){
    for(int i = 0;i < (*TPC3f).size();i++){
        int agent = (*TPC3f)[i];
        if(2 * setValue(S, agent) >= mms[agent]){
            allocateBagf(S, agent, TPC3f, TPC3s, TPC3b);
            return true;
        }
    }
    for(int i = 0;i < (*TPC1).size();i++){
        int agent = (*TPC1)[i];
        if(4 * (setValue2(allocatedItems[agent], S, agent)) >= 3 * mms[agent]){
            allocateBag(S, agent);
            allocateBag1(agent, TPC1);
            return true;
        }
    }
    for(int i = 0;i < (*TPC2).size();i++){
        int agent = (*TPC2)[i];
        if(4 * (setValue2(allocatedItems[agent], S, agent)) >= 3 * mms[agent]){
            allocateBag(S, agent);
            allocateBag2(agent, TPC2);
            return true;
        }
    }
    for(int i = 0;i < (*TPC3s).size();i++){
        int agent = (*TPC3s)[i];
        if(4 * (setValue2(allocatedItems[agent], S, agent)) >= 3 * mms[agent]){
            allocateBag(S, agent);
            allocateBags(agent, TPC3s);
            return true;
        }
    }
    for(int i = 0;i < (*TPC3b).size();i++){
        int agent = (*TPC3b)[i];
        for(int j = 0;j < (*TPC3s).size();j++){
            int agent2 = (*TPC3s)[j];
            if(4 * (setValue2(allocatedItems[agent2], S, agent)) >= 3 * mms[agent]){
                allocateBagb(S, agent, agent2, TPC3f, TPC3s, TPC3b);
                return true;
            }
        }
    }
    return 0;
}

void bagFilling(Graph g3){
    vector<int> TPC1 = findTPC1();
    TPC1 = findTopologicalOrder(TPC1);
    vector<int> TPC2 = findTPC2();
    TPC2 = findTopologicalOrder(TPC2);
    vector<int> TPC3s = findTPC3s(g3);
    TPC3s = findTopologicalOrder(TPC3s);
    vector<int> TPC3b = findTPC3b(g3);
    vector<int> TPC3f = findTPC3f(g3);
    vector<int> S;
    S.clear();
    for(int i = 1;i <= m;i++){
        if(allocation[i])
            continue;
        S.push_back(i);
        if(!feasiblityCheck(S, &TPC1, &TPC2, &TPC3s, &TPC3b, &TPC3f)){
            continue;
        }
        S.clear();
    }
}

void solve(){
    allocateVeryHeavyItems();
    allocateVeryHeavyPairs();
    Graph g1 = buildC1();
    Graph g2 = refineC1(g1);
    Graph g3 = buildC2C3(g1);
    refineC2C3();
    bagFilling(g3);
}

void writeOutput(){
    cout << "Allocation:" << endl;
    for(int i = 1;i <= n;i++){
        cout << "Allocation of agent " << i << " : ";
        for(int j = 0;j < allocatedItems[i].size();j++)
            cout << allocatedItems[i][j] << " ";
        cout << endl;
    }
}

int main(){
    readInput();
    solve();
    writeOutput();
    return 0;
}