I. k-goodness
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For an array $$$a$$$ of integers, let's denote $$$m_0$$$ as the maximum possible sum of a subarray $$$a_l, a_{l+1}, ..., a_r$$$ for some $$$1 \leq l \leq r \leq n$$$ such that $$$a_i \geq 0$$$ for all $$$l \leq i \leq r$$$, and $$$m_1$$$ as the minimum possible sum of a subarray $$$a_l, a_{l+1}, ..., a_r$$$ for some $$$1 \leq l \leq r \leq n$$$ such that $$$a_i \leq 0$$$ for all $$$l \leq i \leq r$$$. An empty subarray should also be considered, it has sum $$$0$$$.

Define k-goodness of an array over a pair $$$x, y$$$ as the maximum value of $$$xm_0 - ym_1$$$ if you are allowed to $$$change$$$ $$$the$$$ $$$sign^\dagger$$$ of at most k elements of the array.

You are given an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$ along with $$$m$$$ queries. Each query is described by a pair of integers $$$x_i, y_i$$$ and you have to determine the k-goodness of the array for each pair $$$x_i, y_i$$$.

$$$^\dagger$$$Changing the sign of a number means multiplying the number with $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ $$$-$$$ the number of test cases.

The first line of each test case contains two integers $$$n,$$$ $$$k$$$ and $$$m$$$ $$$(1 \leq n \leq 5000, 0 \leq k \leq n, 1 \leq m \leq 5000)$$$ $$$-$$$ the length of the array, the goodness number and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(-n \leq a_i \leq n)$$$ $$$-$$$ the elements of the array.

The next $$$m$$$ lines of the input contain the queries, the query number $$$i$$$ is written as two integers: $$$x_i, y_i$$$ $$$(0 \leq x_i \leq 10^4, 0 \leq y_i \leq 10^4)$$$.

Additional constraint on the input:

  • the sum of $$$n$$$ over all test cases does not exceed 5000;
  • the sum of $$$m$$$ over all test cases does not exceed 5000;
  • the sum of absolute values of array elements is less than or equal to n, i.e., $$$\sum_{i = 1}^n abs(a_i) \leq n$$$.
Output

For each test case, print $$$m$$$ integers, the $$$i$$$-th $$$(1 \leq i \leq m)$$$ of which is the answer to the $$$i$$$-th query.

Example
Input
3
5 1 3
2 -1 0 2 0
2 9
2 2
9 2
1 1 3
-1
2 1
1 1
1 2
1 0 3
-1
2 1
1 1
1 2
Output
31 10 45
2 1 2
1 1 2
Note

In first test case: $$$k = 1$$$ is given, so we are allowed to change the sign of at most one element.

Consider the 1st query, its optimal to change the sign of $$$a_1$$$, then the array becomes $$$[-2, -1, 0, 2, 0]$$$, then $$$m_0 = 2$$$ (sum of subarray $$$a_3, a_4$$$) and $$$m_1 = -3$$$ (sum of subarray $$$a_1, a_2$$$). Then k-goodness $$$=$$$ $$$2(2) - 9(-3)$$$ $$$=$$$ $$$31$$$.

Consider the 2nd query, its optimal to change the sign of $$$a_2$$$, then the array becomes $$$[2, 1, 0, 2, 0]$$$, then $$$m_0 = 5$$$ (sum of subarray $$$a_1, ..., a_4$$$) and $$$m_1 = 0$$$ (sum of subarray $$$a_5$$$). Then k-goodness $$$=$$$ $$$2(5) - 2(0)$$$ $$$=$$$ $$$10$$$.