A21304.最佳挤奶

FJ最近买了1个新仓库, 内含N 个挤奶机,1 到N 编号并排成一行。

挤奶机i 每天能产出M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用

(当然, 两端点处的机器分别只有一个与之相邻的机器)。

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

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

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

• 第 1 行：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 台机器，初始产奶量为 1、2、3、4、5。在第 1 天，机器 5 更新为输出 2 个单位的牛奶，依此类推。

第一天，最佳牛奶量为 2+4 = 6（也可以达到 1+3+2）。第二天，最佳量为 7+4 = 11。在第三天，最佳量为10+3+2=15。