Mark and Toys

Mark and Jane are very happy after having their first kid. Their son is very fond of toys. Therefore, Mark wants to buy some toys for his son. But he has a limited amount of money. But he wants to buy as many toys as he can. So, he is in a dilemma and is wondering how he can maximize the number of toys he can buy. He has N items in front of him, tagged with their prices and he has only K rupees.

Now, you being Mark’s best friend have the task to help him buy as many toys for his son as possible.

Input Format
The first line will contain two inputs N and K, followed by a line containing N integers

Output Format
Maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

4

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.

-------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define M 100
int partition(int A[],int f,int l)
{
int i=f,j,x,temp;
x=A[l];
 for(j=f;j<l;j++)
 {
   if(A[j]<x)
   {
     temp=A[j];
     A[j]=A[i];
     A[i]=temp;
     i++;
   }
 }
    A[l]=A[i];
    A[i]=x;
return i;
}

void Sort(int A[],int f,int l)
{
 if(f<l)
 {
 int q=partition(A,f,l);
 Sort(A,f,q-1);
 Sort(A,q+1,l);
 }  
}



void CountTotal(int A[],int N,int K)
{
    int total=0,count=-1,i;
    Sort(A,0,N-1);
    for(i=0;i<N;i++)
    {
        if(total<K)
        {
          total+=A[i];
          count++;
        }
        else 
        {
            printf("%d",count); break;
        }
    
    }
}
int main() 
{
   int A[M],K,i,N;
    scanf("%d %d",&N,&K);
    for(i=0;i<N;i++)
      scanf("%d",&A[i]);

    CountTotal(A,N,K);
    return 0;
}