#include <bits/stdc++.h>
# define clr(x,a)        memset(x,a,sizeof(x))
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define deb2(x, y)      cout<<"("<<#x<<", "<<#y<<")==("<<x<<", "<<y<<")\n";
# define pb              push_back
# define sc              scanf
# define pr              printf
# define nd              second
# define tc              int t; cin>>t; while(t--)
# define rev(s)          reverse(s.begin(),s.end())
# define linija          cout<<"___________\n";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mxN=10005, mxM=5005, mxStates=25;
const long long mod=998244353, inf = 1e9;
template<typename T> T nzd(T a, T b){if(b==0) return a;else return nzd(b, a%b);}
template<typename T> T nzs(T a, T b){return(a*(b/nzd(a,b)));}
template<typename T> T stepenuj(T e, T n){T x=1,p=e;while(n){if(n&1)x=(x*p)%mod;p=(p*p)%mod;n>>=1;}return x;}
template<typename T> inline T na2(T x){return x*x;}

int n, m, s, cost[mxN], BR_ITER, br_swapova;;
int pom_scenes[mxM], cnt[mxN], first_scene[mxN], start_cnt[mxN];
bool done[mxN];
vi scenes[mxM], next_target;
pair<ll, int> brp[mxN];
map <int, pii> map_cs;
mt19937 mt;
uniform_int_distribution<int> dist;
priority_queue<pair<ll, int>> qju;
chrono::high_resolution_clock::time_point start, ende;
pii swapovi[3000];


struct State{
   vi perm;
   ll score;
   State(){
      perm.resize(m);
      for(int i = 1; i <= m; i++)
         perm[i-1] = i;
   }
   int& operator[](int i) {
      if (i < 0 || i >= (int)perm.size()) {
         throw out_of_range("Index out of range");
      }
      return perm[i];
   }
   bool operator<(const State& other) const {
      return score < other.score;  // Smallest score first
   }
}sol, s2, old_sol;

void input(){
   int x, y;
   freopen("star.in", "r", stdin);
   //freopen("star.00.in", "r", stdin);
   sc("%d %d", &n, &m);
   for(int i = 1; i <= n; i++){
      sc("%d", &cost[i]);
      brp[i].second = i;
   }
   for(int i = 1; i <= m; i++){
      sc("%d", &x);
      s += x;
      for(int j = 1; j <= x; j++){
         sc("%d", &y);
         start_cnt[y]++;
         scenes[i].pb(y);
      }
   }

   sol.perm.resize(m);
   for(int i = 1; i <= m; i++){
      sol.perm[i-1] = i;
   }

   BR_ITER = 2;
   random_device rd;
   mt = mt19937(rd());
   dist = uniform_int_distribution<int>(0, m-1);
}

void calc_score_state(State& curr){
   map_cs.clear();
   for(int i = 1; i <= m; i++){
      for(int x : scenes[curr[i-1]]){
         if(!map_cs[x].first) map_cs[x].first = i;
         map_cs[x].second = i;
      }
   }
   curr.score = 0;
   for(auto it = map_cs.begin(); it != map_cs.end(); it++){
      curr.score += (it->second.second - it->second.first + 1LL) * cost[it->first];
   }
}

int num_digits(int number) {
    return number > 0 ? (int)log10(number) + 1 : 1;
}

void cout_score(State& sol){
   int width = num_digits(n);
   bool hasElement[mxN];
   cout << "States\n";
   for(int j = 0; j < m; j++){
      clr(hasElement, 0);
      for(int x: scenes[sol[j]])
         hasElement[x] = true;
      cout << "|";
      for (int i = 1; i <= n; ++i) {
         if (hasElement[i]) {
             printf("%*d,", width, i); // Use dynamic width for alignment
         }
         else {
             printf("%*s,", width, " "); // Print empty spaces with the same width
         }
      }
      printf("|\n"); // Move to the next row
   }
   printf("\n"); // Move to the next row
}

void output(){
   calc_score_state(sol);
   //cout_score(sol);
   cout << "Score: " << sol.score << endl;
   freopen("star.out", "w", stdout);
   for(int i = 0; i < m; i++)
      pr("%d ", sol[i]);
   cout << "\n";
}

inline int get_random(){
   return dist(mt);
}

inline bool ide(const int& actor, const int& scene){
   for(int i: scenes[scene]){
      if(i == actor) return 1;
   }
   return 0;
}

int choose_target(bool pola_po_pola = 0){
   int target = 0;
   while(1){
      if(done[qju.top().second]){
         qju.pop();
         continue;
      }
      target = qju.top().second;
      qju.pop();

      return target;
   }
}

void prepare_pq(){
   while(qju.size()) qju.pop();
   clr(cnt, 0);
   clr(done, 0);
   for(int i = 1; i <= n; i++){
      cnt[brp[i].second] = start_cnt[brp[i].second];

      brp[i].first = (-1LL)*start_cnt[brp[i].second]*cost[brp[i].second];

      qju.push(brp[i]);
   }


   for(int i = 1; i <= m; i++){
      pom_scenes[i] = i;
   }
}

void update_pq(const int& x){
   for(int num: scenes[x]){
      cnt[num]--;
      if(cnt[num] > 0){
         qju.push(make_pair(-1LL*cnt[num]*cost[num], num));
      }
   }
}

void optimizuj_pocetak(int l){
   int poc = 0, nl = 0;
   bool ima;
   for(int target: next_target){
      //cout << "next target: " << target << endl;
      nl = poc = 0;
      //deb(l);
      for(int i = 0; i < l; i++){
         ima = false;
         for(int j: scenes[sol[i]]){
            if(j == target){
               ima = true;
               break;
            }
         }
         if(ima) continue;

         //exit(214);
         swap(sol[poc], sol[i]);
         poc++;
         nl++;
      }
      //cout_score(sol);
      //deb(nl);
      //cout << endl;
      l = nl;
      if(l == 0) break;
   }
}

int fake_sol[2*mxM], rf, lf;
ll score_right, score_left;

void make_sol(){
   int br = 0;
   for(int i = lf+1; i < rf; i++){
      sol[br] = fake_sol[i];
      br++;
   }
}

ll calc_fake_score(){
   map_cs.clear();
   for(int i = lf+1; i < rf; i++){
      for(int x : scenes[fake_sol[i]]){
         if(!map_cs[x].first) map_cs[x].first = i;
         map_cs[x].second = i;
      }
   }
   ll ret = 0;
   for(auto it = map_cs.begin(); it != map_cs.end(); it++){
      ret += (it->second.second - it->second.first + 1LL) * cost[it->first];
   }
   return ret;
}

void manage_fake_sol(int scene){
   //cout << "manage sol: ";
   if(lf == rf){
      lf = m-1;
      rf = m+1;
      fake_sol[m] = scene;
      //cout << "here\n";
   }
   else{
      fake_sol[lf] = scene;
      lf--;
      score_left = calc_fake_score();
      lf++;

      fake_sol[rf] = scene;
      rf++;
      score_right = calc_fake_score();
      rf--;

      //cout << score_left << " " << score_right << endl;

      if(score_right < score_left){
         fake_sol[rf] = scene;
         rf++;
         //cout << "go right\n";
      }
      else{
         //cout << "go left\n";
         fake_sol[lf] = scene;
         lf--;
      }
   }
}

void solve(const bool flag){
   int kraj = m, br = 0, target;
   prepare_pq();
   int l, r;
   lf = rf = -1;
   bool fake_uslov = (s <= 20000);
   if(n == 500 && s == 20000){
      fake_uslov = false;
   }


   //cout << "solve\n";
   //deb(kraj);

   while(1){
      target = choose_target();
      //cout << "target -> " << target << endl;
      for(int j = 1; j <= kraj; j++){
         //cout << pom_scenes[j] << " ";
         if(ide(target, pom_scenes[j])){
            //cout << "ide nekako\n";
            if(fake_uslov) manage_fake_sol(pom_scenes[j]);
            else sol[br++] = pom_scenes[j];

            for(int num: scenes[pom_scenes[j]]){
               cnt[num]--;
               if(cnt[num] > 0){
                  qju.push(make_pair(-1LL*cnt[num]*cost[num], num));
               }
            }

            swap(pom_scenes[kraj], pom_scenes[j]);
            j--;
            kraj--;

            break;
         }
      }

      /*
      if(pocetak == 1 && !flag){
         optimizuj_pocetak(br);
      }*/

      if(kraj == 0) break;
   }
   if(fake_uslov) make_sol();
}

int find_prvi(int& target){
   for(int j = 0; j < m; j++){
      for(int x: scenes[sol[j]]){
         if(x == target){
            return j;
         }
      }
   }
   return -1;
}

int find_zadnji(int& target){
   for(int j = m-1; j >= 0; j--){
      for(int x: scenes[sol[j]]){
         if(x == target){
            return j;
         }
      }
   }
   return -1;
}

bool exist_in_scene(int actor, int scene){
   if(scene >= m) return 0;
   for(int x: scenes[scene]){
      if(x == actor) return 1;
   }
   return 0;
}

void optimizacija_swapuj_u_prazno(){
   int prvi, zadnji;
   ll prev_score;

   calc_score_state(sol);
   prev_score = sol.score;
   //cout << "pre == " << sol.score << endl;

   for(int i = 1; i <= n; i++){
      prvi = find_prvi(i);
      zadnji = find_zadnji(i);

      if(prvi == -1 || zadnji == -1) continue;

      for(int j = prvi+1; j <= zadnji; j++){
         if(j <= prvi) continue;
         if(prvi >= zadnji) continue;
         if(!exist_in_scene(i, sol[j])) continue;

         swap(sol[prvi], sol[j]);
         calc_score_state(sol);

         if(sol.score > prev_score) swap(sol[prvi], sol[j]);
         else{
            prev_score = sol.score;
            do{
               prvi++;
               if(prvi == m) break;
            }while(exist_in_scene(i, sol[prvi]));
         }
      }
   }
   calc_score_state(sol);
}

void uporedi(){
   calc_score_state(s2);
   //cout << s2.score << " " << sol.score << endl;
   if(s2.score < sol.score){
      //cout << "Bolji je\n";
      sol = s2;
   }
}

void rotiraj_na_pola(){
   old_sol = sol;
   s2 = sol;
   calc_score_state(sol);
   int br;
   for(int i = 0; i < (m-1); i++){
      br = 0;
      for(int j = m-1; j > i; j--){
         s2[br++] = old_sol[j];
      }
      for(int j = 0; j <= i; j++){
         s2[br++] = old_sol[j];
      }

      uporedi();
   }
}

void brute_force(){
   int a, b;

   for(int i = 0; i < (m-1); i++){
      for(int j = i+1; j < m; j++)
         swapovi[++br_swapova] = make_pair(i, j);
   }
   calc_score_state(sol);
   ll prev_score = sol.score;

   int old[55];
   for(int i = 0; i < m; i++) old[i] = sol[i];

   while(1){
      for(int i = 1; i < br_swapova; i++){
         for(int j = i+1; j <= br_swapova; j++){
            swap(sol[swapovi[i].first], sol[swapovi[i].second]);
            swap(sol[swapovi[j].first], sol[swapovi[j].second]);

            calc_score_state(sol);

            if(sol.score < prev_score){
               prev_score = sol.score;
            }
            else{
               swap(sol[swapovi[j].first], sol[swapovi[j].second]);
               swap(sol[swapovi[i].first], sol[swapovi[i].second]);
            }

            ende = chrono::high_resolution_clock::now();
            auto duration = chrono::duration_cast<chrono::milliseconds>(ende - start);
            if(duration.count() >= 4700) return;
         }

      }
   }
}

int main(){
   start = chrono::high_resolution_clock::now();
   input();

   solve(1);

   if(n == 10) brute_force();
   else if(s <= 20000) rotiraj_na_pola();
   else solve(0);

   if(m <= 100){
      optimizacija_swapuj_u_prazno();
      optimizacija_swapuj_u_prazno();
   }



   output();

   return 0;
}
//249847732
//1418916557