Kanjus Sammy

0

0 votes
Medium
Problem

Sammy wishes to pursue education in a foreign university after completing his undergraduation. Because of very high fees, he is forced to take education loan from banks. Every bank can lend maximum of pi principal amount with a rate of interest of ri%.
Sammy is smart and wants to minimise the total interest to be paid. In case there exist more than one combination of banks for which the total interest is minimum, choose the one involving minimum number of banks.

INPUT:-
The first line consist of an integer n ,representing the number of banks available.
Each of the next n line consist of one integer and one real number, pi, ri representing principal amount and the rate of interest in % respectively.
Next line consist of an integer q representing the number of queries.(which can be considered as the number of colleges which he may wish to apply)
Each next q line consist of the fees of ith college.

OUTPUT:-
For each college/query, print the number of banks which he may contact inorder his compelete education fees gets covered with minimum interest.
Incase for more than one combination of banks if the interest is same then consider the combination with least number of banks.
In case if no such combination of banks exists, print "Loan cannot be granted" (without quotes).

CONSTRAINTS:-
1<=n<=100000
1<= pi <=100000
1<= ri <=100
1<=q<=100

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?