在一家繁忙的电子元件制造厂中，车间主管小 A 负责优化一排 N 台精密电子元件加工机的运行。这些机器从左至右依次编号为 1 到 N，第 i 台机器在标准条件下每天可加工出 C_i 件合格电子元件。

由于设备负载问题，若相邻两台机器同一天启动，便会因热量干扰引发故障，影响生产安全。小 A 每天可以选择任意多台机器启动，但相邻机器不能同时启动。

工厂计划连续运行 D 天，每天的清晨都会调整一台机器的单日产量。请帮助小 A 通过合理生产调度，计算出 D 天最多总加工电子元件的总量。

第一行输入两个正整数 N 和 D。

第 2 至 N+1 行，每行一个正整数 C_i，表示初始每台机器的加工能力。

接下来的 D 行，每行两个正整数 P_j 和 M_j，表示第 j 天清晨将编号为 P_j 的机器的单日产量调整为 M_j。

一行一个整数，表示 D 天最多总加工电子元件的总量。

样例说明

初始配置下，5 台机器加工能力分别为 1、2、3、4、5。

• 第 1 天，将第 5 台机器的单日加工能力调整为 2。每台机器单日加工零件为 1、2、3、4、2，可选用第 2、4 台得 2+4=6 件，或第 1、3、5 台得 1+3+2=6 件。
• 第 2 天，将第 2 台机器的单日加工能力调整为 7。每台机器单日加工零件为 1、7、3、4、2，可选用第 2、4 台得 7+4=11 件。
• 第 3 天，将第 1 台机器的单日加工能力调整为 10。每台机器单日加工零件为 10、7、3、4、2，可选用第 1、3、5 台得 10+3+2=15 件。

最多总加工电子元件的总量累计 6+11+15=32 件。

数据范围

对于 100\% 的数据，满足 1 ≤ N ≤ 40000，1 ≤ D ≤ 50000，1 \le C_i \le 10^9，1 \le P_j \le N，1 \le M_j \le 10^9。

月赛线段树25年11月