// submasks taken from https://cp-algorithms.com/algebra/all-submasks.html #include using namespace std; #define all(x) x.begin(), x.end() typedef long long ll; const int mod = 1e9 + 7; int a[18], D[17], I[17], party_I[1 << 17], party_D[1 << 17]; int dp[17][1 << 17]; int n, t, s; vector max_days; int f(int i, int mask) { if (i == s) return 0; if (dp[i][mask] != -1) return dp[i][mask]; int ret = 0; for (int submask = mask; submask; submask = (submask - 1) & mask) { if (party_D[submask] <= max_days[i]) { ret = max(ret, party_I[submask] + f(i + 1, mask ^ submask)); } } return dp[i][mask] = ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> t; s = min(n, t); for (int i = 0; i < n; i++) { int x; cin >> x; if (x != 0) { a[0] += 1; a[min(x, s) + 1] -= 1; } if (x == 0 || i == n - 1) { for (int j = 1; j <= s; j++) { a[j] += a[j - 1]; max_days.push_back(a[j]); } memset(a, 0, sizeof a); } } for (int i = 0; i < t; i++) { cin >> D[i] >> I[i]; } for (int mask = 0; mask < (1 << t); mask++) { for (int k = 0; k < t; k++) { if (mask & (1 << k)) { party_I[mask] += I[k]; party_D[mask] += D[k]; } } } sort(all(max_days)); reverse(all(max_days)); memset(dp, -1, sizeof dp); cout << f(0, (1 << t) - 1); }