服务器需求
题号：NC54046
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小多计划在接下来的n天里租用一些服务器，所有的服务器都是相同的。接下来n天中，第i天需要a_i台服务器工作，每台服务器只能在这n天中工作m天，这m天可以不连续。

但是计划不是一成不变的，接下来有q次修改计划（修改是永久的），每次修改某一天k的需求量a_k。

小多希望知道每次修改之后，最少需要多少台服务器。

点击下载大样例

输入描述:

第一行三个正整数n,m,q，分别表示计划的天数，每台服务器能工作的天数和修改次数。

随后一行n个非负整数，第i个数字a_i表示原计划第i天需要多少台服务器工作。

随后q行，每行两个正整数p_i,c_i，表示把第p_i天需要的服务器数目改成c_i。

输出描述:

第一行输出原计划需要的最少服务器数量。

随后q行，每行输出对应的修改之后，需要的最少的服务器的数量。
示例1

输入

复制 
5 3 2
1 1 1 1 1
1 2
2 3

输出

复制 
2
2
3

说明

未修改时，可以租用2台服务器，分别安排给{1,4,5}和{2,3}这些天。

当第一次修改时，第一天需要两台服务器，需求变为了2 1 1 1 1，故可以安排成{1,2,3}和{1,4,5}，满足所有的需求。

第二次修改时，第二天需要三台服务器，需求变为了2 3 1 1 1。可以安排三台服务器，每台服务器安排的日子分别为{1,2,3},{1,2,4}和{2,5}，这样可以满足所有天的需求。

备注:

对于 100% 的数据 有 。