Description

题目描述

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

第 $i$ 台挤奶机当天可以产出 $M_i$ 单位的牛奶。不幸的是，这些机器安装得过于紧密，导致如果某一天使用了机器 $i$，与其相邻的两台机器当天就无法使用。Farmer John 可以自由安排使用哪些机器。

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

Input Format

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

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

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

Output Format

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

5 3 
1 
2 
3 
4 
5 
5 2 
2 7 
1 10 

32 

Hint

初始状态下有 $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$ 单位。