#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
const int maxn = 1003; const int maxm = 10003; const dint dinf = 0x3f3f3f3f3f3f3f3fll;
int n, m, ne[maxn]; dint a[maxm][maxn];
void pivot(int e, int p) { int fr(n + 1); for (int i = n; i >= 0; – i) if (a[p][i]) { ne[fr] = i; fr = i; } ne[fr] = -1; a[p][e] = -1; for (int i = 0; i <= m; ++ i) if (i != p) { int rat(a[i][e] / a[p][e]); a[i][e] = 0; for (int j = ne[n + 1]; j > -1; j = ne[j]) a[i][j] -= rat * a[p][j]; } }
dint simplex() { while (1) { int e, p(-1); dint v(dinf); for (e = 1; e <= n && a[0][e] <= 0; ++ e); if (e > n) return a[0][0]; for (int i = 1; i <= m; ++ i) if (a[i][e] < 0 && a[i][0] < v) v = a[p = i][0]; if (p == -1) return dinf; pivot(e, p); } }
int main() { #ifdef LAEKOV_LOCAL freopen(".in", “r”, stdin); #endif
memset(a, 0, sizeof(a));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i)
scanf(lld, a[0] + i);
for (int i = 1; i <= m; ++ i) {
int k, s, t;
scanf("%d", &k);
while (k --) {
scanf("%d%d", &s, &t);
for (int j = s; j <= t; ++ j)
a[i][j] = -1;
}
scanf(lld, a[i]);
}
printf(lld "\n", simplex());
}