Weighted Necklace

You are given $K$ different colors of beads. A bead of the $i$-th color has a weight $w_i$. You have infinitely many beads of each color. All the beads of the same color have the same weight. You have to answer $q$ independent queries. For each query, you will be given $S$. You have to form a necklace consisting of $n$ beads such that the total weight of the necklace is $S$. You can use any numbe