Fingerpainting Paint Kits

The local toy store sells fingerpainting kits. Each kit contains between three and twelve bottles of paint, one bottle per color, and every bottle holds $50$ ml of its color. All kits are identical: the same set of colors, $50$ ml of each.

These paints have a handy property: if you mix $X$ ml each of any three different colors, you get exactly $X$ ml of gray. The paint is thick and dense, so mixing does not increase the volume — it just gets denser, turning $3X$ ml of colored paint into $X$ ml of gray. None of the base colors is gray, and the only way to make gray is to mix three distinct colors; it does not matter which three.

Emily runs a fingerpainting project with her class every Friday. Given the number of colors in a kit, how much of each color is needed, and how much gray is needed, compute the minimum number of kits required.

The input consists of one or more test cases, followed by a line containing only a single $0$ that marks the end of the input. Each test case is one line of five or more space-separated integers. The first integer $N$ ($3 \le N \le 12$) is the number of colors in a kit. It is followed by $N$ integers, each between $0$ and $1000$, giving the amount of each color needed. The last integer $G$ ($0 \le G \le 1000$) is the amount of gray needed. All amounts are in ml.

For each test case, print on its own line the smallest number of kits sufficient to provide the required amount of every color and of gray. Because all grays are considered equal, obtaining the minimum may require making gray from several different combinations of three distinct colors.