题目描述

农夫约翰最近买了一个新谷仓，里面有${N}$台挤奶机${(1 <= N <= 40000)，}$顺手编号为${1..N}$排成一行。

挤奶机${i}$每天能够抽取${M(i)}$单位的牛奶${(1 <= M(i) <= 100,000)}$。不幸的是，这些机器安装得太近了，如果一 台机器${i}$在某一天正在使用，那么它的两个相邻机器当天不能使用（当然，端点机器只有一个相邻机器）。

农民 约翰可以自由选择不同的机器子集，在不同的日子操作。

农民约翰对计算他在一系列的${D}$天${(1 <= D <= 50000)}$中可以提取的最大牛奶量很感兴趣。在每天开始的时候，他有足够的时间对选定的一台挤奶机${i}$进行维护，从而从那天起改变其每天的牛 奶产量${M(i)}$。

给出这些日常修改的列表，请告诉农民约翰，他在${D}$天内可以生产多少牛奶（注意，这个数字可能不适合${32}$位整数）。${FJ}$最近买了${1}$个新仓库, 内含${N }$个挤奶机,${1 }$到${N }$编号 并排成一行。

挤奶机${i }$每天能产出${M(i) }$单位的奶。不幸的是, 机器装得太近以至于如果一台机器${i }$在某天被使用, 那与它 相邻的两台机器那一天不能被使用 （当然, 两端点处的机器分别只有一个与之相邻的机器）。

${FJ }$可自由选择不同的机器在不同的日子工作。

${FJ}$感兴趣于计算在${D }$天内他能产出奶的最大值。 在每天开始时, 他有足够的时间维护一个选中的挤奶机${i, }$从 而改变它从那天起的每日产奶量${M(i)}$。

给出这些每日的修改,请告诉${FJ}$他${D }$天中能产多少奶。

输入格式

第一行:${N}$和${D}$的值。

第${2 . .1+N}$行:第${i+1}$行包含${M(i)}$的初始值。

第 ${2 + N}$行. .${1+N+D:}$行${1+N+D}$包含两个整数${i}$和${m，}$

表示${Farmer John}$在第${d}$天开始时将${M(i)}$的值更新为${M}$。

输出格式

第${1}$行:${FJ}$在${D}$天内能生产的最大牛奶总量。

样例

输入样例

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

输出样例

32

提示

有${5}$台机器，初始产奶量为${1}$、${2}$、${3}$、${4}$、${5}$。第一天，机器${5}$更新为输出${2}$单位牛奶，以此类推。

第${1}$天的最佳奶量为${2+4 = 6(}$也可达到${1+3+2)}$。

第${2}$天最佳用量为${7+4 = 11}$。第${3}$天，最佳用量为${10+3+2=15}$。