#include<stdio.h>
void insertion_sort(int a[],int n)
{
    int i,j;
    for(j=1; j<n; j++)
    {
        int key =a[j];
        i=j-1;
        while(i>=0 && a[i]<=key)
        {
            a[i+1]=a[i];
            i--;
        }
        a[i+1]=key;
    }

    for(i=0; i<n; i++)
    {
        printf("%d ",a[i]);
    }
    printf("coins are sorted!\n");
}
int main()
{
    int s,num;
    printf("Enter your amount: ");
    scanf("%d",&s);

    int m,i;
    printf("how many coin: ");

    scanf("%d",&m);
    int c[m];
    printf("enter coin values: ");
    for(i=0; i<m; i++)
    {
        scanf("%d",&c[i]);
    }
    insertion_sort(c,m);


            i=0;
            while(s>0)
            {
                if(s>=c[i])
            {
                num = s/c[i];
                printf("%d coin will need %d\n",c[i],num);
                s = s - num*c[i];
            }
            i++;
            }

        }