经典错题。。。因为破坏了全幺模矩阵，线性规划无法保证求出整数解。。。
答案居然不会 LL = =。
const int N = int(1e4) + 9, M = int(1e3) + 9;
struct Simplex {
DB a[N][M];
int n, m;
void pivot(int in, int out) {
REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束
a[out][in] = 1/a[out][in];
REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束
DB t = a[i][in]; a[i][in] = 0;
REP(j, m+1) a[i][j] += t*a[out][j];
}
}
DB run() {
while (true) {
int in=0, out=0; DB Min=OO;
REP_1(i, m) if(sgn(a[0][i])>0) {
in=i;
break;
}
if(!in)return a[0][0];
REP_1(i, n) if(sgn(a[i][in])<0&&a[i][0]/-a[i][in]<Min) {
Min=a[i][0]/-a[i][in];
out=i;
}
if(!out)throw ; //unbounded
pivot(in, out);
}
}
int gao() {
// z b
// c A
RD(m, n); REP_1(i, m) RD(a[0][i]);
REP_1(i, n) {
Rush {
int l, r; RD(l, r);
FOR_1(j, l, r) a[i][j] -= 1;
}
RD(a[i][0]);
}
return run();
}
} fst;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
OT(fst.gao());
}
