Washroom Satisfaction Index

Some guests pick an apartment by counting its washrooms first. Waterbnb wants to take the approximate time each guest spends in a washroom and report a washroom satisfaction index (WSI) for every apartment.

The WSI of one guest is the time that guest waits plus the time that guest spends in the washroom. If two guests use one washroom for 2 minutes and 5 minutes, and a third guest uses it for 3 minutes after them, the WSI of the third guest is $2 + 5 + 3 = 10$ minutes.

The WSI of an apartment is defined like this. First assign the guests to the washrooms: who uses which washroom, and in which order. Once the assignment is fixed you can compute the WSI of every guest, and their sum is the WSI of that assignment. The smallest WSI over all assignments is the WSI of the apartment. Every washroom is free at time 0, and one washroom serves one guest at a time.

Take three guests A, B and C whose washroom times are 3 minutes, 5 minutes and 8 minutes. In an apartment with three washrooms each guest gets a washroom of their own, so the WSI is $3 + 5 + 8 = 16$. In an apartment with two washrooms, putting A then B in washroom 1 and C in washroom 2 gives $(3 + (3 + 5)) + 8 = 19$, while putting B then C in washroom 1 and A in washroom 2 gives $(5 + (5 + 8)) + 3 = 21$. Other assignments exist, but none goes below 19, so the WSI of the apartment with two washrooms is 19.

The time a guest needs in the washroom changes from day to day. Every time one guest's time is updated, compute the WSI of the apartment again.

The first line contains the number of test cases $T$ ($1 \le T \le 16$).

The first line of each test case contains the number of guests $G$ and the number of washrooms $W$ ($1 \le G \le 50000$, $1 \le W \le 50000$).

The second line contains $G$ integers. The $i$-th of them is the time guest $i$ spends in a washroom, between $1$ and $100000$.

The third line contains the number of updates $Q$ ($1 \le Q \le 10000$). Each of the following $Q$ lines contains two integers $p$ and $x$ ($1 \le p \le G$, $1 \le x \le 100000$), meaning that the time of guest $p$ becomes $x$. The updates are applied one after another in the given order.

For each test case, print the test case number on its own line in the form Case k:, where $k$ starts at 1. Then print $Q$ lines holding the WSI of the apartment right after each update, in order. Do not print the WSI of the initial state.