# PAT「1004 To Buy or Not to Buy - Hard Version (35分)」

## 1. 题目

### Description

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence in some cases Eva might have to buy several strings to get all the beads she needs. With a hundred strings in the shop, Eva needs your help to tell her whether or not she can get all the beads she needs with the least number of extra beads she has to pay for.

For the sake of simplicity, let's use the characters in the ranges [0-9], [a-z], and [A-Z] to represent the colors. In sample $1$, buying the $2$nd and the last two strings is the best way since there are only $3$ extra beads. In sample $2$, buying all the three strings won't help since there are three R beads missing.

### Input Specification:

Each input file contains one test case. Each case first gives in a line the string that Eva wants. Then a positive integer $N$ ($\leq 100$) is given in the next line, followed by $N$ lines of strings that belong to the shop. All the strings contain no more than $1000$ beads.

### Output Specification:

For each test case, print your answer in one line. If the answer is Yes, then also output the least number of extra beads Eva has to buy; or if the answer is No, then also output the number of beads missing from all the strings. There must be exactly $1$ space between the answer and the number.

## 2. 题解

### 分析

• 如果所有珠子串都用上仍然无法满足要求，则直接退出 bfs
• 如果 bfs 当前发现多余的珠子比原来的答案还多，则直接剪掉当前分支；如果当前刚好满足要求且多余的珠子数比原来的答案少，则更新当前答案