CF1846G Rudolf and CodeVid-23

A new virus called "CodeVid-23" has spread among programmers. Rudolf, being a programmer, was not able to avoid it. There are $ n $ symptoms numbered from $ 1 $ to $ n $ that can appear when infected. Initially, Rudolf has some of them. He went to the pharmacy and bought $ m $ medicines. For each medicine, the number of days it needs to be taken is known, and the set of symptoms it removes. Unfortunately, medicines often have side effects. Therefore, for each medicine, the set of symptoms that appear when taking it is also known. After reading the instructions, Rudolf realized that taking more than one medicine at a time is very unhealthy. Rudolph wants to be healed as soon as possible. Therefore, he asks you to calculate the minimum number of days to remove all symptoms, or to say that it is impossible.

N/A

N/A

In the first example, we can first apply medicine number $ 4 $ , after which the symptoms will look like "00101". After that, medicine number $ 2 $ , then all symptoms will disappear, and the number of days will be $ 5 + 3 = 8 $ . Another option is to apply the medicines in the order $ 1, 3, 2 $ . In this case, all symptoms will also disappear, but the number of days will be $ 3 + 3 + 3 = 9 $ . In the second example, there are no symptoms initially, so the treatment will take $ 0 $ days. In the third example, there are no options to remove all symptoms.