Maximum Sum of Two Largest in Subarray

You are given an array of length \(N\) where the \(i\)th element is \(a_i\). There are \(Q\) updates. In the \(j\)th update, the element at position \(i_j\) is changed to \(x_j\).

After the initial array is given and after each update, you need to determine the maximum possible sum of the largest and the second largest elements among all contiguous subarrays of length \(K\).

More formally, for every state of the array, consider all contiguous subarrays of length \(K\). For each subarray, let \(M_1\) be the maximum element and \(M_2\) be the second maximum element (assume \(K \ge 2\)). You need to output the maximum value of \(M_1 + M_2\) over all such subarrays.

inputFormat

The first line contains three integers \(N\), \(Q\), and \(K\) \((\geq 2)\), where \(N\) is the length of the array, \(Q\) is the number of updates, and \(K\) is the length of the subarray to consider.

The second line contains \(N\) integers: \(a_1, a_2, \ldots, a_N\), representing the initial array.

Each of the following \(Q\) lines contains two integers \(i_j\) and \(x_j\), indicating that in the \(j\)th update, the element at position \(i_j\) is updated to \(x_j\).

outputFormat

Output \(Q+1\) lines. The first line contains the maximum sum in the initial array and each subsequent line contains the result after each update.

sample

5 3 3
1 2 3 4 5
2 10
4 0
1 6

9
15
15
15