lazy-and-probability

Lazy boy has gone home during his vacations. As it is the season of Holi, his mother expects him to

do some of her work so that she can relax a little bit. However, since lazy boy is lazy, he wants to do

as less work as possible, giving him more time to sleep, as lazy boy loves to sleep. However, he also

knows that he needs to do a minimum amount of work, otherwise he will be scolded by his father

for being too lazy. There are n distinct tasks that her mother asks him to do, and each task has an associated

amount of work with it. Lazy boy knows how much amount of work he needs to do to avoid being

scolded by his father. He wants to do this much amount of work by doing the least number of tasks.

Also, he never does more than two distinct tasks. Lazy boy wants to know what is the minimum

number of tasks he should do so that the total amount of work done by him is equal to the required

amount of work to avoid being scolded. Lazy boy makes q such queries to you, you need to give an

answer for every query.

You will be given an array a, of n elements, giving the amount of work associated with each of the n

tasks, and a number k, meaning the lazy boy never does more than k tasks in total. After that there will be q

queries. For each query, which contains a single number, you need to tell what is the minimum

number of tasks he should do to achieve the amount of work given in the query. If it is not possible

to do so, output “:(” (without quotes).

Note : Lazy boy does at most two of the distinct tasks assigned by his mother, and he does not do more than k
tasks in total. He can repeat a task many times, as long as he does less than or equal to k tasks.

Input :

First line contains two integers n (number of tasks) and k (maximum number of tasks lazy boy

does).

Next line contains n space-separated integers, the array a, giving the amount of work associated

with each task.

Next line contains q, the number of queries.

Each query contains an integer x (the required amount of work to be done).

Output :

For each query, output the minimum number of tasks he should do so that total amount of work

done is equal to x. If it is not possible to do so, print “:(” (without quotes).

Constraints :

n ≤ 5000

k ≤ 20

ai ≤ 10^7

q ≤ 20

x ≤ 2*10^8

Problem setter : Sahil Prakash

SAMPLE INPUT
5 4
1 2 11 12 14
3
1
4
9

SAMPLE OUTPUT
1
2
:(

Explanation

Explaination (for 3 rd query) :
 Since it is not possible to get total amount of work done equal to 9 by

doing only two of the available tasks, not doing more than 4 tasks in total, the ouput is “:(”.

Source: hackerearth | Difficulty: EASY


Solutions: