A2217. 最佳挤奶
编程题
普及/提高-
知识点
题目描述
FJ最近买了1个新仓库, 内含N 个挤奶机,1 到N 编号并排成一行。
挤奶机i 每天能产出M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用
(当然, 两端点处的机器分别只有一个与之相邻的机器)。
FJ 可自由选择不同的机器在不同的日子工作。
FJ感兴趣于计算在D 天内他能产出奶的最大值。在每天开始时, 他有足够的时间维护一个选中的挤奶机i, 从而改变它从那天起的每日产奶量M(i)。
给出这些每日的修改,请告诉FJ他D 天中能产多少奶。
挤奶机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。
* 第 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 天内可以产生的最大牛奶总量。
输入输出样例
输入 #1
5 3 1 2 3 4 5 5 2 2 7 1 10
输出 #1
32
说明/提示
有 5 台机器，初始产奶量为 1、2、3、4、5。在第 1 天，机器 5 更新为输出 2 个单位的牛奶，依此类推。
第一天，最佳牛奶量为 2+4 = 6（也可以达到 1+3+2）。第二天，最佳量为 7+4 = 11。在第三天，最佳量为10+3+2=15。
第一天，最佳牛奶量为 2+4 = 6（也可以达到 1+3+2）。第二天，最佳量为 7+4 = 11。在第三天，最佳量为10+3+2=15。