Help Munna

All submissions for this problem are available.
Munnabhai needs a curtain rod of length L. He already has curtain rods of certain lengths but all are smaller than L. Munnabhai is a frugal man. He decides that if its possible to make a rod of length L by joining the smaller rods, he won't buy a new one. So firstly, given a set of rods, Munnabhai needs to determine whether he can make a rod of length L by joining the available rods(NOTE: If n rods of lengths l1,l2,...,ln are joined together, we get a rod of length l1+l2+...+ln). If this can be done, then he will choose a set of rods such that:
1.) There are minimum number of joints in the final rod of length L.
2.) Munnabhai's storeroom is designed in a way that its infinitely more difficult to keep one larger rod as compared to any number of smaller rods. So he chooses the set accordingly.
(Example: For L=25, 10,10,5 is preferred over 10,9,6 because keeping(in the store or not using) a rod of length 10 is infinitely more difficult than keeping rods of lengths 9 and 6 together.)
Munnabhai gives greater priority to criteria (1) as compared to (2).
Input:
L n l1 p1 l2 p2 . . . . . . ln pn
where, L is the final rod length
n is the number of rod lengths available
l(i) is available rodlength 1<=i<=n
p(i) is the number of rods available of rodlength l(i) 1<=i<=n
Constraint: L>l1>l2>...>ln>0
L,n,l1,l2,...,ln,p1,p2,...,pn are all positive integers
l1*p1 + l2*p2 + ... + ln*pn < 999
Output:
M l1 q1 l2 q2 . . . . . . ln qn
where, M is the minimum number of rods needed
l(i) is available rodlength, 1<=i<=n
q(i) is the number of rods of rodlength l(i) used, 1<=i<=n
If it is not possible to make a rod of length L from the given set of rods, then
Output:
Not possible to make a rod of length L from the given set of rods
Example 1:
Input:
25
4
10 2
9 1
6 1
5 1
Output:
3
10 2
9 0
6 0
5 1
Example 2:
Input:
25
3
10 1
9 1
5 1
Output:
Not possible to make a rod of length 25 from the given set of rods
Author:  pankajb64 
Tags  pankajb64 
Date Added:  9022012 
Time Limit:  0.1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, GO, NODEJS, BF, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 