线段树跌丝袜（D老师写小说写的吃菌子了）

// 灵感菇农场管理日志 - 千早爱音与高松灯篇
// 在MyGO!!!!!乐队的世界里，糖奶龙千早爱音与凑企鹅高松灯发现了一种神奇的"灵感菇"，
// 它能帮助乐队成员突破创作瓶颈。但采摘时需遵守特殊规则：
// 相邻的灵感菇种植点不能同时采摘，否则会引发"旋律冲突"。
// 爱音和灯需要每天计算最优采摘方案，最大化总灵感值。

// 线段树节点结构体：存储每个种植区间的四种采摘状态
struct SegTreeNode {
    long long f00; // 区间左端和右端都不采摘
    long long f01; // 左端不采，右端采摘
    long long f10; // 左端采摘，右端不采
    long long f11; // 左右端都采摘
    SegTreeNode() : f00(0), f01(0), f10(0), f11(0) {}
};

vector<SegTreeNode> segTree; // 灵感菇农场线段树
vector<int> mushroom; // 每个种植点的灵感值

// 合并两个子区间的状态 - 爱音的精密计算与灯的直觉融合
SegTreeNode merge(const SegTreeNode& left, const SegTreeNode& right) {
    SegTreeNode res;
    // 计算f00：左侧终点不采，右侧起点不采
    res.f00 = max(left.f00 + right.f00, left.f01 + right.f00);
    res.f00 = max(res.f00, left.f00 + right.f10);

    // 计算f01：左侧终点不采，右侧起点采摘
    res.f01 = max(left.f00 + right.f01, left.f00 + right.f11);
    res.f01 = max(res.f01, left.f01 + right.f01);

    // 计算f10：左侧终点采摘，右侧起点不采
    res.f10 = max(left.f10 + right.f00, left.f10 + right.f10);
    res.f10 = max(res.f10, left.f11 + right.f00);

    // 计算f11：左侧终点采摘，右侧起点采摘
    res.f11 = max(left.f10 + right.f01, left.f10 + right.f11);
    res.f11 = max(res.f11, left.f11 + right.f01);
    return res;
}

// 构建灵感菇农场线段树 - 初始化每个种植点
void build(int node, int start, int end) {
    if (start == end) {
        // 单个种植点：要么采摘，要么不采
        segTree[node].f00 = 0;          // 不采摘这个点
        segTree[node].f01 = -1e18;      // 非法状态（单点无法一端采一端不采）
        segTree[node].f10 = -1e18;      // 非法状态
        segTree[node].f11 = mushroom[start]; // 采摘这个点，获得全部灵感值
    } else {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid);    // 构建左子树
        build(2 * node + 2, mid + 1, end);  // 构建右子树
        // 合并左右子区间的灵感值方案
        segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]);
    }
}

// 更新种植点的灵感值 - 蘑菇的生长每天都有变化
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        mushroom[idx] = val;  // 更新这个点的灵感值
        segTree[node].f00 = 0;
        segTree[node].f01 = -1e18;
        segTree[node].f10 = -1e18;
        segTree[node].f11 = val;  // 采摘这个点获得新值
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node + 1, start, mid, idx, val);   // 更新左子树
        } else {
            update(2 * node + 2, mid + 1, end, idx, val); // 更新右子树
        }
        // 重新计算合并后的最佳方案
        segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, D;
    cin >> N >> D;  // N个灵感菇种植点，D天管理期
    mushroom.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> mushroom[i];  // 每个种植点的初始灵感值
    }
    
    // 为灵感菇农场建立线段树索引
    int size = 1;
    while (size < N) size <<= 1;
    segTree.resize(2 * size - 1);
    build(0, 0, N - 1);  // 构建初始农场状态
    
    long long total_inspiration = 0;  // 总灵感值累积
    for (int d = 0; d < D; ++d) {
        int i, m;
        cin >> i >> m;  // 每天更新：第i个种植点灵感值变为m
        --i;  // 转为0起始索引
        update(0, 0, N - 1, i, m);  // 更新农场状态
        
        SegTreeNode root = segTree[0];  // 获取整个农场的最优状态
        // 计算当天最大可获取灵感值（四种状态取最优）
        long long max_today = max({root.f00, root.f01, root.f10, root.f11});
        total_inspiration += max_today;  // 累积到总灵感值
        
    }
    cout << total_inspiration << '\n';  // 输出D天获得的总灵感值
    
    return 0;
}