迷之逆序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

MLE 得到了 QAQ 的真传,但 QAQ 为了检验 MLE 智商是否可以真正领悟,于是出了这一道题:给出 n 个数的序列,先把每个数逆序(如 120 变为 21,123 变为 321),将会产生 n 个新数,我们把它称作序列 A。

之后对序列 A 中的 n-1 个数进行 q 次操作,每次操作将会把序列 A 上的某个数替换成另一个数,并询问序列 A 中任取连续的一段数,如何取才能使这段数的和最大,请你输出最大值。

Input

输入数据有多组(数据组数不超过 100)。

对于每组数据:

  • 第一行输入 n, q (1 <= n <= 10000, 1 <= q <= 100) 分别表示数字个数和操作次数
  • 接下来的一行输入 n 个正整数,最大不超过 10000
  • 接下来的 q 行,每行输入 2 个整数,分别为要替换的数的位置 xi (1 <= xi <= n) 和要修改的值 yi (-10000 <= yi <= 10000)

当 n = 0 时输入结束。

Output

对于每组数据第一行输出 "Case #x:" (不包括引号,冒号后无空格),x 表示当前为第几组数据。之后对应 q 次操作每次操作输出一行,表示查询的答案。

Sample Input

5 2
1 2 3 4 5
2 -5
2 5
3 3
45 12 32
3 -5
1 5
2 10
0

Sample Output

Case #1:
12
18
Case #2:
75
26
15

Hint

请大家仔细核对 "Case #x:",建议复制样例输出的模式以防输出时不符合题目要求而导致的 Wrong Answer。

Source

【2016级《程序设计基础(B)II》期末上机考试-第一场】MLE_kenan