import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Pickpockets {

	static class Team {
		int workingDays = 0;
		int income = 0;
		boolean assigned = false;
	}

	static int H, T;
	static List<Integer> limits = new ArrayList<>();
	static List<Team> teams = new ArrayList<>();
	static int best = 0;

	public static void main(String[] args) throws IOException {
		readData();

		int maxLevel = 0;
		for (Integer l : limits) if (l > maxLevel) maxLevel = l;

		teams.sort((o1, o2) -> Integer.compare(o2.income, o1.income));

		try {
			tryElement(maxLevel, 0);
		} catch (Exception ignored) {
			
		}
		System.out.println(best);
	}

	static boolean tryElement(int level, int start) {
		while (true) {
			int startHole = start;
			while (startHole < H && limits.get(startHole) < level) startHole++;
			int endHole = startHole;
			while (endHole < H && limits.get(endHole) >= level) endHole++;

			if (startHole >= H) {
				level--;
				if (level == 0) {
					return true;
				}
				start = 0;
				continue;
			}

			boolean found = false;
			int cnt = 0;
			for (Team t : teams) {
				if (!t.assigned && endHole - startHole >= t.workingDays) {
					t.assigned = true;
					if (tryElement(level, startHole + t.workingDays)) {
						int value = teams.stream().filter(team -> team.assigned).mapToInt(team -> team.income).sum();
						if (value > best) best = value;
						cnt++;
						if (cnt > 5) throw new ArithmeticException("too much");
						found = true;
					}
					t.assigned = false;
				}
			}
			return found;
		}
	}

	public static void readData() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer line1 = new StringTokenizer(reader.readLine(), " ");
		H = Integer.parseInt(line1.nextToken());
		T = Integer.parseInt(line1.nextToken());

		StringTokenizer line2 = new StringTokenizer(reader.readLine(), " ");
		for (int i = 0; i < H; ++i) {
			limits.add(Integer.valueOf(line2.nextToken()));
		}

		for (int i = 0; i < T; ++i) {
			StringTokenizer line = new StringTokenizer(reader.readLine(), " ");
			Team team = new Team();
			team.workingDays = Integer.parseInt(line.nextToken());
			team.income = Integer.parseInt(line.nextToken());
			teams.add(team);
		}
	}
}