#include <bits/stdc++.h>
#pragma optimize ("g", on)
#define ll long long
#define LIM 20000000
using namespace std;
int N, M, br; ///BROJ GLUMACA, SCENA, GLUMACA U SCENI
mt19937_64 rng;
int SOL[5005], SOLCURR[5005]; ///RESENJE ZA SIMIJA
double CoolingRate = 0.995;
char BUFFER[LIM], *pos;
ll bbr;
char broj[15];
struct Glumac
{
    ll idx, Cena; ///IME I PLATA
    vector<int>V;///SCENE U KOJIMA JE GLUMAC
}A[10005];
bool MAT[10005][5005];
ll L[10005], R[10005];
struct Scene
{
    int idx; ///INDEX SCENE
    vector<int>V; ///GLUMCI
}S[5005];
ll MinScore, Score; ///MINIMALNA RESENJA
set<int> Set[10005];
inline ll Scoring(int *SOL)
{
    memset(L, 0, sizeof(L));

    for(int i = 1; i <= M; i++)
    {
       for(int x : S[SOL[i]].V){if(L[x] == 0)L[x] = i;R[x] = i;}

    }
    ll RET = 0;
    for(int i = 1; i <= N; i++)RET += (R[i] - L[i] + 1LL) * A[i].Cena;
    return RET;
}
ll BetterIter;
ll iter;
inline void CheckScore()
{
    Score = Scoring(SOLCURR);
    if(Score >= MinScore)return;
    swap(SOLCURR, SOL);
    MinScore = Score;
    return;
}
inline void SET(int i, int j)
{
//    cout << "NADJIN ZUB\n";
    ll MasperScore = Score;
    for(int x : S[SOLCURR[i]].V)
    {
        if(MAT[x][SOLCURR[j]])continue;
        MasperScore -= (*Set[x].rbegin() - *Set[x].begin() + 1LL) * A[x].Cena;
        Set[x].erase(i);
        Set[x].insert(j);
        MasperScore += (*Set[x].rbegin() - *Set[x].begin() + 1LL) * A[x].Cena;
    }
    for(int x : S[SOLCURR[j]].V)
    {
        if(MAT[x][SOLCURR[i]])continue;
        MasperScore -= (*Set[x].rbegin() - *Set[x].begin() + 1LL) * A[x].Cena;
        Set[x].erase(j);
        Set[x].insert(i);
        MasperScore += (*Set[x].rbegin() - *Set[x].begin() + 1LL) * A[x].Cena;
    }
    if(MasperScore < Score)
    {
        BetterIter = iter;
//        cout << "ARONOV ZUB\n";
        swap(SOLCURR[i], SOLCURR[j]);
        Score = MasperScore;
        return;
    }
    else
    {
        for(int x : S[SOLCURR[i]].V)
        {
            if(MAT[x][SOLCURR[j]])continue;
            Set[x].erase(j);
            Set[x].insert(i);
        }
        for(int x : S[SOLCURR[j]].V)
        {
            if(MAT[x][SOLCURR[i]])continue;
            Set[x].erase(i);
            Set[x].insert(j);
        }
        return;
    }
}
inline int getint()
{
    char c;
    while((c = *pos++) < '0');
    unsigned long long x = c - '0';
    while((c = *pos++) >= '0')x = x * 10 + c - '0';
    return x;
}
inline void Input()
{
    N = getint();
    M = getint();
    for(int i = 1; i <= N; i++)A[i].Cena = getint(), A[i].idx = i;
    for(int i = 1; i <= M; i++)
    {
        br = getint();
        S[i].idx = i;

        for(int j = 1; j <= br; j++)
        {
            int x;
            x = getint();
            MAT[x][i] = true;
            Set[x].insert(i);
            S[i].V.push_back(x);
        }
    }
    return;
}
inline void RAND()
{
    clock_t KRAJ = clock() + CLOCKS_PER_SEC * 4.85;
    for(int i = 1; i <= M; i++)SOLCURR[i] = i;
    Score = Scoring(SOLCURR);
    iter = 0;
    while(clock() < KRAJ)
    {
        if(iter - BetterIter > M * M)
        {
            CheckScore();
            shuffle(SOLCURR + 1, SOLCURR + M + 1, rng);
            for(int i = 1; i <= N; i++)Set[i].clear();
            for(int i = 1; i <= M; i++)
            {
                for(int x : S[i].V)Set[x].insert(i);
            }
            Score = Scoring(SOLCURR);
        }
        iter++;
        int i = rng() % M + 1;
        int j = rng() % M + 1;
        if(i == j)continue;
        SET(i, j);
//        if(Score != Scoring(SOLCURR)){cout << Score << ' ' << Scoring(SOLCURR) << '\n';exit(1);}
    }
}
inline void buff(int b)
{
    int p = 0;
    while(b > 0){
    broj[++p] = b % 10 + 48;
    b /= 10;
  }
  for (int i = p; i >= 1; i--) BUFFER[bbr++] = broj[i];
  BUFFER[bbr++] = 32;
}
inline void Output(int *SOL)
{
    for(int i = 1; i <= M; i++)buff(SOL[i]);
    fwrite(BUFFER, 1, bbr, stdout);
}
int main(){
    rng.seed(1);
    freopen("star.in", "r", stdin);
    fread(BUFFER, 1, LIM, stdin);
    pos = BUFFER;
    Input();
    for(int i = 1; i <= M;i++)SOL[i] = i;
    MinScore = Scoring(SOL);
    RAND();
    CheckScore();
    cout << MinScore << endl;
    cout << iter << endl;
    freopen("star.out", "w", stdout);
    Output(SOL);
return 0;
}