Cylinders

Byteasar urgently needs to measure exactly $l$ millilitres of water, but the only glassware he could buy was a pair of identical defective cylinders. Each cylinder has a capacity of $x_n$ millilitres and is marked with scales at exactly the same values $x_1, x_2, \dots, x_n$ (in millilitres); the water level can only be read at these marked heights.

Both cylinders start empty. In one unit of time Byteasar may perform any one of the following actions:

• fill a cylinder from the tap until its water level reaches one of that cylinder's scales;
• pour water from a cylinder into the sink until its level reaches one of that cylinder's scales;
• pour water from one cylinder into the other until the source cylinder's level reaches one of its scales;
• pour water from one cylinder into the other until the destination cylinder's level reaches one of its scales.

A transfer between cylinders is only possible when the destination does not overflow. Determine the minimum number of actions needed to obtain exactly $l$ millilitres of water in one of the cylinders, or report that it is impossible.

The first line contains one integer $n$ ($3 \le n \le 25$): the number of scales on each cylinder.

The second line contains a strictly increasing sequence of integers $x_1, x_2, \dots, x_n$ separated by single spaces: the scale values. It is guaranteed that $x_1 = 0$ and that $x_n$ ($x_n \le 100000$) equals the capacity of each cylinder.

The third line contains one integer $l$ ($0 \le l \le x_n$): the amount of water to be measured.

If Byteasar cannot measure exactly $l$ millilitres, output a single line containing the word NIE. Otherwise, output a single integer: the minimum number of actions required.