How can I efficiently randomly select items from a dictionary that meet my requirements?

So at the moment, I have a large dictionary of items. Might be a little confusing, but each of these keys have different values, and the values themselves correspond to another dictionary.

I need to make sure that my random selection from the first dict covers all possible values in the second dict. I'll provide a rudimentary example:

Dict 1 = {key1: (A, C), key2: (B, O, P), key3: (R, T, A), and so on

Dict 2 = {A: (1, 4, 7), B: (9, 2, 3), C: (1, 3), etc

I need a random selection of Dict 1 to give me a coverage of all numbers from 1 - 10 in Dict 2 values.

At the moment, I am selecting 6 random keys from Dict 1, taking all the numbers that those letters would correspond with, and comparing that set to a set of the numbers from 1 - 10. If the selection isn't a subset of 1 - 10, select 6 more random ones and try again, until I have 1 - 10.

Now, this works, but I know it's far from efficient. How can I improve this method?

I am using Python.