Mued is finally home for summer vacation after surviving yet another semester of the mighty CS Undergrad Program. Oh! So long he had waited for this moment. He is looking forward to fructify the plan of not leaving his room for next 6-7 days.
On one fine morning of the vacation, when the room temperature was just perfect to cover himself with a comfortable sheet and do a lie down marathon; his father gave him the most annoying job he could think of – paying bills!! He was given coins of value , , …, and was told to pay some pending bills on different stores. Bill of -th store is .
“There is no point of wondering why I am only given coins”, he thought. Rather he decided to make some fun out of it. He liked the sweet sound of coins in his pocket. And he wanted to enjoy it on his way back home too. The best way to do this would be to pay all the bills using minimum number of coins and keep the rest in his pocket. The storekeepers won’t give him any change as expected. “Whatever, can’t be more cruel than my old man”, said he with a grin on his face.
Being a talented programmer himself, Mued can find out the minimum number of coins needed to pay all the bills. He doesn’t need your help. You are here just to play along.
There will be () test cases.
Each case starts with a positive integer () denoting the number of coins. Then comes the value of each coin (). Next, there will be an integer () denoting the number of stores followed by the bill of each store ().
Print case number and the minimum number of coins needed. Print -1 if it is not possible to pay all the bills with given coins.
Input | Output |
---|---|
2 6 1 2 3 4 5 6 2 9 3 6 1 2 3 4 5 6 3 4 4 4 | Case 1: 3 Case 2: -1 |