CCT A5 - Kefa hates coins

Kefa hates coins and thinks that coins are a currency of the poor.

She has N coins with her, ith of them having the value Ai.
She goes to a shop to buy M gifts, with the price of ith gift being Pi.

She wants to get rid of as many coins as she can and she buys the gift one by one from the 1st one to the Mth one. She adopts the following strategy while buying any particular gift i : She wants to give the shopkeeper a total of X coins whose value sum up to K such that -

1. K ≥ Pi
2. X is maximized
3. K - Pi is minimized

She does not consider other gifts while buying a particular gift i.e. while buying every gift she tries her best to satisfy the above conditions for that gift.

Your task is, given the array A and the array P, for every gift, find and print the values of X and K, or print -1 -1 if she will not be able to buy the gift at all.

INPUT

First line contains two numbers N and M.
Second line contains the array A of size N.
Third line contains the array P of size M.

INPUT

Print M lines of output, for every gift two integers on a new line.
The two integers should denote the values of X and K while buying that gift optimally.
If it is not possible to buy a particular gift with available coins, print "-1 -1"

CONSTRAINTS

1 ≤ N, M ≤ 105
1 ≤ Ai, Pi ≤ 105

Sample Input 0

10 5
1 2 3 4 5 1 2 3 4 5
6
6
6
6
6

Sample Output 0

4 6
2 6
2 8
2 10
-1 -1

Solution :

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner sc = new Scanner (System.in);

        int a = sc.nextInt();

        int b = sc.nextInt();

        int ar[] = new int[a];

        int ar1[] = new int[b];

        for(int i = 0; i<a; i++ )

            ar[i] = sc.nextInt();

        for(int i = 0; i<b; i++ )

            ar1[i] = sc.nextInt();

        Arrays.sort(ar);

        int v[] =new int [a];

        int cc=0;

        for(int i = 0; i<b; i++ )

        {

            int sum=0;

            int count=0;

            for(int j = cc; j<a; j++ )

            {

                if(v[j]==0)

                {

                sum+=ar[j];

                v[j]=1;

                count++;

                cc++;

                }

                

                if(sum>=ar1[i])

                    break;                

            }

            if(count!=0&&sum!=0)

                System.out.println(count+" "+sum);

            else

                System.out.println("-1 -1");

                

        }

        

        

    }

}