#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 310

int n,m,a[N],c[N],w[N],len[N];

long long f[N][N][N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4565.in","r",stdin);

    freopen("bzoj4565.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    memset(f,,sizeof(f));

    for (int i=;i<=n;i++) a[i]=read(),f[i][i][a[i]]=,len[i]=(i-)%(m-)+;

    for (int i=;i<(<<m);i++) c[i]=read(),w[i]=read();

    for (int k=;k<=n;k++)

        for (int i=;i<=n-k+;i++)

        {

            int j=i+k-;

            for (int d=j-;d>=i;d-=m-)

                if (len[k]!=)

                    for (int v=;v<(<<len[k]);v++)

                        f[i][j][v]=max(f[i][j][v],f[i][d][v>>]+f[d+][j][v&]);

                else

                    for (int u=;u<(<<m-);u++)

                    f[i][j][c[u<<]]=max(f[i][j][c[u<<]],f[i][d][u]+f[d+][j][]+w[u<<]),

                    f[i][j][c[u<<|]]=max(f[i][j][c[u<<|]],f[i][d][u]+f[d+][j][]+w[u<<|]);

        }

    for (int i=;i<(<<m);i++) f[][n][]=max(f[][n][],f[][n][i]);

    cout<<f[][n][];

    return ;

}