int N, M;
int tree[4 * MXN], lazy[4 * MXN];

int merge(int x, int y) { return max(x, y); }

void push(int i, int l, int r) {
    if (lazy[i] == 0) return;

    tree[i] += (r - l + 1) * lazy[i];
    if (l != r) {
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
    }
    lazy[i] = 0;
}

void modify(int i, int l, int r, int ql, int qr, int val) {
    if (l > qr || r < ql) return;
    push(i, l, r);
    if (l >= ql && r <= qr) {
        lazy[i] += val;
        push(i, l, r);
    }

    int mid = (l + r) >> 1;
    modify(2 * i, l, mid, ql, qr, val);
    modify(2 * i + 1, mid + 1, r, ql, qr, val);

    tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}