### 问题描述 小齐刚刚购买了一个新的牛棚，里面有 $N$ 台挤奶机，方便编号为 $1$ 到 $N$，并且排列成一排。 第 $i$ 台挤奶机每天能够挤出 $M(i)$ 单位的牛奶（$1 \leq M(i) \leq 100,000$）。不幸的是，挤奶机安装得非常靠近，因此在特定的一天，如果挤奶机 $i$ 在使用中，它的两台相邻的挤奶机就不能使用（当然，端点的挤奶机只有一个相邻的挤奶机）。小齐可以选择在不同的天使用不同的挤奶机子集。 小齐希望计算在连续的 $D$ 天内他能够挤出的最大牛奶量。每天开始时，他有足够的时间对选定的挤奶机 $i$ 进行维护，从而改变其每天的牛奶产量 $M(i)$。给定这些每日修改的列表，请告诉小齐在 $D$ 天内他最多能够生产多少牛奶（注意，这个数字可能不适合 $32$ 位整数）。 ### 输入格式 第 $1$ 行：两个整数 $N$ 和 $D$。 接下来的$N$行：每行一个整数，表示挤奶机 $i$ 的初始牛奶产量 $M(i)$。 接下来的$D$行：每行两个整数 $i$ 和 $m$，表示在第 $d$ 天开始时，小齐将挤奶机 $i$ 的产量更新为 $m$。 ### 输出格式 小齐在 $D$ 天内最大能够生产的牛奶总量。 ### 样例输入 ``` 5 3 1 2 3 4 5 5 2 2 7 1 10 ``` ### 样例输出 ``` 32 ``` ### 评测数据规模 $1 \leq N, D \leq 40,000$。