#include<fstream>
#include<cstdio>
#include<iostream>
#define DN 2000005
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
ofstream fout("gordonramsay.out");
int n,k,a[DN],r[DN],nr,rez[DN],c[DN],rt=1,poz,rt2,fr[(1<<12)],d[DN],z;
long long t,ma,ma2,sum,f;
pair<pair<int,int>,int>b[DN];
FILE *fin=fopen("gordonramsay.in","r");
const unsigned maxb=30000192;
unsigned ptr=maxb;
char buf[maxb];
inline unsigned getint()
{
    unsigned nr=0;
    while(!(buf[ptr]>='0'&&buf[ptr]<='9'))
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    while(buf[ptr]>='0'&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    return nr;
}
void ve(int r[DN],int nr)
{
    for(int i=0;i<(1<<11);i++)
        fr[i]=0;
    for(int i=1;i<=nr;i++)
    {
        z=(r[i]&((1<<11)-1));
        fr[z]++;
    }
    for(int i=1;i<=(1<<11);i++)
        fr[i]=fr[i-1]+fr[i];
    for(int i=(1<<11);i>0;i--)
        fr[i]-=fr[i-1];
    fr[0]=0;
    for(int i=1;i<=nr;i++)
    {
        z=(r[i]&((1<<11)-1));
        fr[z]++;
        d[fr[z]]=r[i];
    }
    for(int i=0;i<(1<<11);i++)
        fr[i]=0;
    for(int i=1;i<=nr;i++)
    {
        z=(d[i]>>11);
        z=(z&((1<<11)-1));
        fr[z]++;
    }
    for(int i=1;i<=(1<<11);i++)
        fr[i]=fr[i-1]+fr[i];
    for(int i=(1<<11);i>0;i--)
        fr[i]-=fr[i-1];
    fr[0]=0;
    for(int i=1;i<=nr;i++)
    {
        z=(d[i]>>11);
        z=(z&((1<<11)-1));
        fr[z]++;
        r[fr[z]]=d[i];
    }
}
int main()
{
    n=getint();
    k=getint();
    for(int i=1;i<=n;i++)
        a[i]=getint();
    for(int i=1;i<=k;i++)
    {
        b[i].x.x=getint();
        b[i].x.y=getint();
        b[i].y=getint();
    }
    int s[k+5][n+5];
    for(int i=1;i<=k;i++)
        for(int j=0;j<=n;j++)
            if(j==0)
                s[i][j]=0;
            else
                if(a[j]!=i)
                    s[i][j]=s[i][j-1];
                else
                    s[i][j]=s[i][j-1]+1;
    for(int l=1;l<=n;l++)
    {
        f=0;
        for(int i=1;i<=k;i++)
        {
            nr=0;
            for(int j=1;j<=n;j+=l)
            {
                poz=min(n,j+min(l,b[i].y)-1);
                nr++;
                r[nr]=s[i][poz]-s[i][j-1];
            }
            if((1<<11)>nr)
                sort(r+1,r+nr+1);
            else
                ve(r,nr);
            ma2=0;
            rt2=0;
            sum=0;
            for(int j=1;j<=nr;j++)
            {
                t=1LL*(nr-j+1)*1LL*r[j]*1LL*b[i].x.y+sum-1LL*b[i].x.x*1LL*nr*1LL*r[j];
                sum+=1LL*r[j]*1LL*b[i].x.y;
                if(t>ma2)
                {
                    ma2=t;
                    rt2=r[j];
                }
                else
                    if(t<ma2)
                        break;
            }
            f+=ma2;
            c[i]=rt2;
        }
        if(f>ma)
        {
            ma=f;
            rt=l;
            for(int i=1;i<=k;i++)
                rez[i]=c[i];
        }
    }
    fout<<ma<<'\n';
    fout<<rt<<'\n';
    for(int i=1;i<=k;i++)
        fout<<rez[i]<<' ';
}