Jamal is trying to install a new app on his smart phone, but he is getting an error message:

“Memory is full”.

He loves his already installed apps, so he wants to remove the minimum number of them to be

able to install the new app.

Assume that his phone memory is k MBs, the new app size is m MBs and that there are n

installed apps. You are given a list of n positive integers representing the sizes of the installed

apps.

Find the minimum number of apps that should be removed.

Input

The first line of input contains one integer T, the number of test cases(1≤T≤128).

Each test case begins with three integers:k,m,n(1≤m≤k≤32,768)and(1≤n≤100).The next

line contains n space-separated integers representing the sizes of the installed apps.

Output

For each test case, print the minimum number of apps Jamal has to remove to be able to install.

thenewapp.

input

2

7 7 5

1 2 1 1 1

14 13 5

1 2 2 1 2

output

5

4

题意：

一个人的手机内存不足，已知他的手机内存和手机里每个app所占的内存，问：如果要再下载一个app，最少要卸载几个app。这道题主要就是贪心，一直卸载当前占内存最大的app，直到空闲内存大于等于所需要下载的app的内存，统计一下卸载了几个app就好了。注意排序时不要越界。

代码：

#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace  std;

int  main()

{    

      int  a[105];   

      int  k, m, n, i, t, j, s;    

      scanf("%d", &t);    

      for (j = 0;j < t;j ++)

      {

            scanf("%d%d%d", &k, &m, &n);

            s = k;

            for (i = 0;i < n;i ++)

            {

            scanf("%d", &a[i]);

            s -= a[i];

            }

            sort(a, a+n);

            for (i = n-1;i >= 0;i --)

            {

            s += a[i];

            if (s >= m)

            break;

           }

           printf("%d\n", n-i);

           memset(a, 0, sizeof(a));

     }

     return  0;

}