욕실 만족도 지수

숙소를 고를 때 욕실이 몇 개인지 먼저 따지는 손님이 있다. Waterbnb는 손님이 욕실에서 보내는 대략의 시간을 입력받아 숙소마다 욕실 만족도 지수(WSI)를 계산해 주려고 한다.

한 손님의 WSI는 그 손님이 기다린 시간과 욕실을 쓴 시간의 합이다. 한 욕실을 두 손님이 각각 2분과 5분 동안 쓰고 세 번째 손님이 그 뒤에 3분 동안 쓴다면, 세 번째 손님의 WSI는 $2 + 5 + 3 = 10$분이다.

숙소의 WSI는 이렇게 정한다. 먼저 손님을 욕실에 배정한다. 누가 어느 욕실을 어떤 순서로 쓰는지 정하면 모든 손님의 WSI를 계산할 수 있고, 그 합이 이 배정의 WSI다. 가능한 모든 배정 중 가장 작은 값이 숙소의 WSI다. 욕실은 모두 0분에 비어 있고, 한 욕실은 한 번에 한 손님만 쓴다.

손님이 A, B, C 세 명이고 욕실 사용 시간이 각각 3분, 5분, 8분인 경우를 보자. 욕실이 3개인 숙소에서는 셋이 서로 다른 욕실을 써서 WSI가 $3 + 5 + 8 = 16$이 된다. 욕실이 2개인 숙소에서는 1번 욕실을 A 다음에 B가 쓰고 2번 욕실을 C가 쓰면 WSI가 $(3 + (3 + 5)) + 8 = 19$이고, 1번 욕실을 B 다음에 C가 쓰고 2번 욕실을 A가 쓰면 WSI가 $(5 + (5 + 8)) + 3 = 21$이다. 다른 배정도 있지만 19보다 작은 값은 나오지 않으므로 욕실이 2개인 숙소의 WSI는 19다.

손님이 욕실에서 보내는 시간은 그날 사정에 따라 달라진다. 어떤 손님의 시간이 바뀔 때마다 숙소의 WSI를 다시 계산하라.

첫 줄에 테스트 케이스 개수 $T$가 주어진다 ($1 \le T \le 16$).

각 테스트 케이스의 첫 줄에는 손님 수 $G$와 욕실 수 $W$가 주어진다 ($1 \le G \le 50000$, $1 \le W \le 50000$).

둘째 줄에는 $G$개의 정수가 주어진다. $i$번째 수는 $i$번 손님이 욕실에서 보내는 시간이고 $1$ 이상 $100000$ 이하다.

셋째 줄에는 갱신 횟수 $Q$가 주어진다 ($1 \le Q \le 10000$). 이어지는 $Q$개의 줄에는 각각 두 정수 $p$와 $x$가 주어진다 ($1 \le p \le G$, $1 \le x \le 100000$). $p$번 손님의 시간이 $x$로 바뀐다는 뜻이며, 갱신은 주어진 순서대로 누적되어 적용된다.

각 테스트 케이스마다 먼저 테스트 케이스 번호를 Case k: 형식으로 한 줄에 출력한다. $k$는 1부터 시작한다. 그다음 $Q$개의 줄에 각 갱신 직후 숙소의 WSI를 순서대로 출력한다. 처음 상태의 WSI는 출력하지 않는다.