#P1779C. Least Prefix Sum

Least Prefix Sum

Description

Baltic, a famous chess player who is also a mathematician, has an array a1,a2,,ana_1,a_2, \ldots, a_n, and he can perform the following operation several (possibly 00) times:

  • Choose some index ii (1in1 \leq i \leq n);
  • multiply aia_i with 1-1, that is, set ai:=aia_i := -a_i.

Baltic's favorite number is mm, and he wants a1+a2++ama_1 + a_2 + \cdots + a_m to be the smallest of all non-empty prefix sums. More formally, for each k=1,2,,nk = 1,2,\ldots, n it should hold that a1+a2++aka1+a2++am.a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m.

Please note that multiple smallest prefix sums may exist and that it is only required that a1+a2++ama_1 + a_2 + \cdots + a_m is one of them.

Help Baltic find the minimum number of operations required to make a1+a2++ama_1 + a_2 + \cdots + a_m the least of all prefix sums. It can be shown that a valid sequence of operations always exists.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t100001 \leq t \leq 10\,000). The description of the test cases follows.

The first line of each test case contains two integers nn and mm (1mn21051 \leq m \leq n \leq 2\cdot 10^5) — the size of Baltic's array and his favorite number.

The second line contains nn integers a1,a2,,ana_1,a_2, \ldots, a_n (109ai109-10^9 \leq a_i \leq 10^9) — the array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052\cdot 10^5.

For each test case, print a single integer — the minimum number of required operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t100001 \leq t \leq 10\,000). The description of the test cases follows.

The first line of each test case contains two integers nn and mm (1mn21051 \leq m \leq n \leq 2\cdot 10^5) — the size of Baltic's array and his favorite number.

The second line contains nn integers a1,a2,,ana_1,a_2, \ldots, a_n (109ai109-10^9 \leq a_i \leq 10^9) — the array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052\cdot 10^5.

Output

For each test case, print a single integer — the minimum number of required operations.

样例输入 1

6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873

样例输出 1

1
1
0
0
3
4

Note

In the first example, we perform the operation a4:=a4a_4 := -a_4. The array becomes [1,2,3,4][-1,-2,-3,4] and the prefix sums, [a1, a1+a2, a1+a2+a3, a1+a2+a3+a4][a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4], are equal to [1,3,6,2][-1,-3,-6,-2]. Thus a1+a2+a3=6a_1 + a_2 + a_3=-6 is the smallest of all prefix sums.

In the second example, we perform the operation a3:=a3a_3 := -a_3. The array becomes [1,2,3,4][1,2,-3,4] with prefix sums equal to [1,3,0,4][1,3,0,4].

In the third and fourth examples, a1+a2++ama_1 + a_2 + \cdots + a_m is already the smallest of the prefix sums — no operation needs to be performed.

In the fifth example, a valid sequence of operations is:

  • a3:=a3a_3 := -a_3,
  • a2:=a2a_2 := -a_2,
  • a5:=a5a_5 := -a_5.

The array becomes [2,3,5,5,20][-2,-3,5,-5,20] and its prefix sums are [2,5,0,5,15][-2,-5,0,-5,15]. Note that a1+a2=5a_1+a_2=-5 and a1+a2+a3+a4=5a_1+a_2+a_3+a_4=-5 are both the smallest of the prefix sums (and this is a valid solution).