题目描述

有 $n$ 道菜品，从左到右第 $i$ 道菜品的价格是 $a_i$ 元。现在需要从左到右依次购买这些菜品。

对于一道菜品，每消费 $c$ 元，就可以得到一张代金券，代金券的价值是 1 元。使用代金券不算在消费的钱数内。

设当前你拥有 $A$ 元钱和 $B$ 张代金券，当前菜品的价格是 $P$ 元。在这道菜品上消费了 $x$ 元，使用了$y$ 张代金券，那么要求：

1. $0 ≤ x ≤ A，0 ≤ y ≤ B$。
2. $x + y = P$。

在购买菜品后，你会得到$\left\lfloor\dfrac{x}{c}\right\rfloor$张代金券，也就是你拥有的钱数会变为 $A − x$，拥有的代金券张数会变为 $B − y +$\left\lfloor\dfrac{x}{c}\right\rfloor$。

有 $Q$ 次修改，每次修改给出 $x, y$，将 $a_x$ 修改为 $y$。

在所有修改前和每次修改后，都需要输出，你初始时最少需要多少钱才能买下所有菜品。

输入格式

第一行三个整数 $n, Q, c$ 含义如上。

第二行 $n$ 个整数 $a_1, a_2, . . . , a_n$ 表示菜品的价格。

接下来 $Q$ 行每行两个整数表示一次修改。

输出格式

$Q + 1$ 行每行一个整数表示最少的钱数。

样例

input1

3 3 4
5 1 2
2 4
1 1
2 2

output1

7
9
6
5

数据范围与提示

对于 30% 的数据满足 $n, Q ≤ 2000$。 对于另外 10% 的数据满足 $c = 1$。 对于所有数据，满足 $1 ≤ n, Q ≤ 3 × 10^5，1 ≤ a_i, y ≤ 10^{12}，1 ≤ c ≤ 10^9$。