N, M = map(int, input().split()) e = list(map(int, input().split())) v, w = [], [] for _ in range(M): vi, wi = map(int, input().split()) v.append(vi) w.append(wi) K = 1<>i&1: sum_v[S] += v[i] sum_w[S] += w[i] dp = [0]*(K*(N+1)) rev = [{} for _ in range(N+1)] for i in range(N): for S in range(K): U = K - 1 - S T = U while True: if sum_w[T] <= e[i] and dp[(i+1)*K+(S|T)] < dp[i*K+S]+sum_v[T]: # (i, S) -> (i+1, S|T) dp[(i+1)*K+(S|T)] = dp[i*K+S]+sum_v[T] rev[i+1][S|T] = S if T == 0: break T = (T-1)&U m = max(dp[N*K+S] for S in range(K)) S = 0 while dp[N*K+S] != m: S += 1 ans = [[] for _ in range(N)] for i in range(N, 0, -1): T = rev[i].get(S, S) for j in range(M): if (S^T)>>j&1: ans[i-1].append(j+1) S = T print(m) for a in ans: print(len(a), *a)