Kitchen Measurements

You are following a recipe and need to measure an exact volume of liquid. The kitchen holds several cups of different sizes. No cup carries any marking other than its total capacity, and none of them matches the volume you want. You start with the biggest cup full. To know exactly how much liquid sits in each cup at every moment, you only use pours: take a cup that still holds liquid and pour it into another cup, continuing until the receiving cup is full or the pouring cup is empty, whichever happens first.

For a simple example, start with a full cup of capacity $5$ and one more cup of capacity $2$, with the goal of leaving $3$ units in the largest cup. Pour from the larger cup into the smaller one. The pour stops when the small cup reaches its capacity of $2$, which leaves exactly $3$ units in the large cup. See Figure 1(a).

Figure 1: Pouring between cups

For a second example, take four cups of capacities $9$, $6$, $3$, and $2$, start with the largest one full and the rest empty, and aim for $8$ units in the largest cup. For ease of discussion, call the cup of capacity $9$ the 9-cup and name the other cups the same way. The 6-cup and the 2-cup hold $8$ units together, so you can fill both from the 9-cup, empty the remaining $1$ unit of the 9-cup into the 3-cup, then pour the full 6-cup and the full 2-cup back. See Figure 1(b). That plan pours a total volume of $6 + 2 + 1 + 6 + 2 = 17$. You can reach the same goal another way: pour $3$ units from the 9-cup into the 3-cup, leaving $6$ units in the 9-cup, fill the 2-cup from the 3-cup, leaving $1$ unit in the 3-cup, and pour the full 2-cup back into the 9-cup. The 9-cup then holds exactly $8$ units and the total poured volume is only $3 + 2 + 2 = 7$. See Figure 1(c).

For a last example, take cups of capacities $11$, $10$, $7$, $4$, and $2$ with the 11-cup full, and aim for $10$ units in the 11-cup. You can fill the 10-cup, empty the remaining $1$ unit into another cup, and pour the full 10-cup back into the 11-cup, as in Figure 2(a). Those three pours transfer a total volume of $10 + 1 + 10 = 21$. Figure 2(b) shows a sequence with more steps that pours less liquid.

Figure 2: More pouring

The input is a single line of positive integers.

$n\ c_1\ c_2\ \dots\ c_n\ V$

There are $n$ cups with $2 \le n \le 5$, and their capacities satisfy $64 \ge c_1 > c_2 > \dots > c_n \ge 1$. The value $V < c_1$ is the desired volume. The largest cup, the one of capacity $c_1$, starts full and every other cup starts empty. The goal is to get exactly volume $V$ into the largest cup.

Print the minimum amount of liquid that must be poured to achieve the goal. If the goal cannot be achieved, print impossible.