Master Plan

nadimnesar Unlock The Algorithm, Spr...
Limits 3s, 1.0 GB

Because of Eid-ul-Fitr, there is a BIG OFFER at your nearest super shop. You have decided to go shopping with your family at that super shop.

In the super shop, there are NN types of products. The rule of the offer is that each person can buy each type of product only once, but they can buy multiple products of different types. Every ithi’th product have price PiP_i and weight WiW_i written on it.

You and your family want to buy as many valuable products as possible, but there is a limitation. Since each person is of a different age, they cannot carry the same amount of weight. Your have FF persons in your family including you. You know ithi’th person can carry maximum FWiFW_i amount of weight.

Now your role is to create a master plan and calculate the maximum value of products that you and your family can buy from the offer.


The first line contains one integer TT (1T103)(1 \le T \le 10^{3}) — the number of test cases. Then TT test cases follow.

Each test case begins with a single integer NN (1N100)(1 \le N \le 100) — indicates the number of products. Then follows NN lines, each containing two integers: PiP_i (1Pi100)(1 \le P_i \le 100) and WiW_i(1Wi30)(1 \le W_i \le 30) — indicate the price of the product and the weight of the product respectively. Next line contains a single integer FF (1F100)(1 ≤ F ≤ 100) — the number of persons in your family including you. Next FF lines contains maximal weight FWiFW_i (1FWi30)(1 ≤ FW_i ≤ 30) that can carry by ithi’th person from your family.


For every test case output a single integer — the maximal value of products you and your family can buy using the offer.


32 20
8 10
93 30

Be careful about the newline(‘\n’) at the end.


Login to submit.


69% Solution Ratio
iffatul_anonEarliest, 4M ago
jahid_hridoyFastest, 0.0s
jahid_hridoyLightest, 4.9 MB
jahid_hridoyShortest, 995B
Toph uses cookies. By continuing you agree to our Cookie Policy.