题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

32

提示

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

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

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