#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define rint register int
#define endl '\n'

const int N = 3e2 + 5;
const int M = 256;
const int inf = 0x3f3f3f3f;

int n, m;
int c[N], w[N], a[N];
int f[N][N][M];
int g[2];
int ans;

signed main()
{
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}

	for (rint i = 0; i < (1 << m); i++)
	{
		scanf("%d%d", &c[i], &w[i]);
	}

	memset(f, 0xcf, sizeof f);

	for (rint i = 1; i <= n; i++)
	{
		f[i][i][a[i]] = 0;
	}

	for (rint len = 1; len < n; len++)
	{
		for (rint l = 1; l <= n; l++)
		{
			int r = l + len;
			int x = len % (m - 1);

			if (!x)
			{
				x = m - 1;
			}
			for (rint k = l; k < r; k += m - 1)
			{
				for (rint p = 0; p < (1 << x); p++)
				{
					f[l][r][p << 1] = std::max(f[l][r][p << 1], f[l][k][p] + f[k + 1][r][0]);
					f[l][r][p << 1 | 1] = std::max(f[l][r][p << 1 | 1], f[l][k][p] + f[k + 1][r][1]);
				}
			}

			if (x == m - 1)
			{
				g[0] = -inf;
				g[1] = -inf;
				for (rint p = 0; p < (1 << m); p++)
				{
					int k = c[p];
					g[k] = std::max(g[k], f[l][r][p] + w[p]);
				}
				f[l][r][0] = g[0];
				f[l][r][1] = g[1];
			}
		}
	}

	for (rint i = 0; i < (1 << m); i++)
	{
		ans = std::max(ans, f[1][n][i]);
	}

	printf("%d", ans);

	return 0;
}