题目描述

Farmer John 最近购买了一个新谷仓，内有 $N$ 台挤奶机，从左到右标为 $1 \sim N$。

第 $i$ 台挤奶机当天可以产出 $M_i$ 单位的牛奶。不幸的是，这些机器安装得过于紧密，导致如果某一天使用机器 $i$，机器 $i - 1$（$i \neq 1$ 时）与机器 $i + 1$（$i \neq n - 1$ 时）无法使用。Farmer John 可以自由安排使用哪些机器。

他想计算出，在 $D$ 天内能产出的最大牛奶量。在每一天开始时，Farmer John 会对一台挤奶机进行维护，即改变一台机器的 $M$ 值。给定维护列表，求这 $D$ 天内最多能生产多少单位的牛奶。注意，$32$ 位整型可能不适合用于储存答案。

输入格式

第一行两个正整数 $N, D$。

第 $2 \sim N + 1$ 行，每行一个正整数 $M_i$。

对于接下来的第 $d$ 行，每行两个正整数 $i, m$，表示在第 $d$ 天开始时有一次操作 $M_i \gets m$。

输出格式

一行一个正整数，表示答案。

说明/提示

初始状态下有 $5$ 台挤奶机，$M_i$ 分别为 $1, 2, 3, 4, 5$。第 $1$ 天开始时，$M_5$ 被更新为 $2$，以此类推。

• 第 $1$ 天，$M_i$ 分别为 $1, 2, 3, 4, 2$，可以选择机器 $2, 4$ 以获得当天 $2 + 4 = 6$ 单位的牛奶，或选择机器 $1, 3, 5$ 得到相同的答案（$1 + 3 + 2 = 6$）。
• 第 $2$ 天，$M_i$ 分别为 $1, 7, 3, 4, 2$，选择机器 $2, 4$ 以获得当天 $7 + 4 = 11$ 单位的牛奶。
• 第 $3$ 天，$M_i$ 分别为 $10, 7, 3, 4, 2$，选择机器 $1, 3, 5$ 以获得当天 $10 + 3 + 2 = 15$ 单位的牛奶。

总产奶量为 $6 + 11 + 15 = 32$ 单位。

### 题目描述

Farmer John 最近购买了一个新谷仓，内有 $N$ 台挤奶机，从左到右标为 $1 \sim N$。

第 $i$ 台挤奶机当天可以产出 $M_i$ 单位的牛奶。不幸的是，这些机器安装得过于紧密，导致如果某一天使用机器 $i$，机器 $i - 1$（$i \neq 1$ 时）与机器 $i + 1$（$i \neq n - 1$ 时）无法使用。Farmer John 可以自由安排使用哪些机器。

他想计算出，在 $D$ 天内能产出的最大牛奶量。在每一天开始时，Farmer John 会对一台挤奶机进行维护，即改变一台机器的 $M$ 值。给定维护列表，求这 $D$ 天内最多能生产多少单位的牛奶。注意，$32$ 位整型可能不适合用于储存答案。

### 输入格式

第一行两个正整数 $N, D$。

第 $2 \sim N + 1$ 行，每行一个正整数 $M_i$。

对于接下来的第 $d$ 行，每行两个正整数 $i, m$，表示在第 $d$ 天开始时有一次操作 $M_i \gets m$。

### 输出格式

一行一个正整数，表示答案。

### 说明/提示

初始状态下有 $5$ 台挤奶机，$M_i$ 分别为 $1, 2, 3, 4, 5$。第 $1$ 天开始时，$M_5$ 被更新为 $2$，以此类推。

- 第 $1$ 天，$M_i$ 分别为 $1, 2, 3, 4, 2$，可以选择机器 $2, 4$ 以获得当天 $2 + 4 = 6$ 单位的牛奶，或选择机器 $1, 3, 5$ 得到相同的答案（$1 + 3 + 2 = 6$）。
- 第 $2$ 天，$M_i$ 分别为 $1, 7, 3, 4, 2$，选择机器 $2, 4$ 以获得当天 $7 + 4 = 11$ 单位的牛奶。
- 第 $3$ 天，$M_i$ 分别为 $10, 7, 3, 4, 2$，选择机器 $1, 3, 5$ 以获得当天 $10 + 3 + 2 = 15$ 单位的牛奶。

总产奶量为 $6 + 11 + 15 = 32$ 单位。