Cashback on payment methods (e.g. credit card) is a common term nowadays. That is, if you pay using some payment method, you’ll get some percentage of money back. For the sake of this problem, let’s consider credit card as the only payment method.
Usually, Cashback is expressed in percentage, per month.
$X\%$ cashback for using a card means if you spend
$100$ BDT, you’ll get
$X$ BDT back in your account, at the end of that month.
A common condition among almost all companies is that - If you spend at least
$M$ amount monthly, you’ll get
$X\%$ cashback, otherwise
$Y\%$ cashback on total expense made through that card.
As different companies have different values for
$M, X, Y$, if you have more than one card, it can be challenging to figure out the optimal expense strategy to maximize cashback.
Given description of
$C$ credit cards and
$E$ expenses for next month. Help to distribute the expenses among the cards to get maximum amount of cashback.
$T$ - number of test cases to follow. Each test case contains:
$C$ denoting the number of credit cards.
Each of next
$C$ lines contains an integer
$2$ decimal numbers
$Y$ as stated above.
$E$ denoting number of expenses to follow.
$E$ space separated integers denoting expenses of upcoming month.
$1 \leq T \leq 10$
$1 \leq C \leq 10$
$0 \leq M \leq 100,000$
$0 \leq X, Y \leq 100$, can contain up to
$2$ decimal place.
$1 \leq E \leq 10$
$1 \leq Each \; individual \; expense \leq 10,000$
For each test case, print one decimal number in a new line- the maximum amount of cashback that can be earned for this test case. The answer will be considered correct if its relative or absolute error doesn't exceed
2 1 0 5 5 4 20 500 30 50 2 800 8 0.25 100 1.5 20 5 10 500 30 240 50