w_count = int(input())
n = int(input())
w = []; p = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    p.append(y)
a = [[0]*w_count for i in range(n)]
for k in range(n):
    for s in range(w_count):
        if s >= w[k]:
            a[k][s] = max(a[k-1][s],a[k-1][s-w[k]]+p[k])
        else: a[k][s] = a[k-1][s]
for i in range(len(a)):
    print(*a[i])
ans = []
def f(k,s,ans):
    print(k,s,ans)
    if a[k][s] == 0 :
        return ans
    if a[k-1][s] == a[k][s]:
        print(1)
        return f(k-1,s,ans)
    else:
        ans.append(k)
        print(2,k,s)
        return f(k-1,s-w[k],ans)   
ans = f(k,s,ans)
print(ans)
s = [p[i]  for i in range(len(p)) if i in ans]
print(sum(s))