16. 量杯問題

量杯問題

題目敘述

實驗室有很多量杯，但取用時不一定有符合需求的容量，因此我們可以使用一種技巧來得到需要的量。比如說現在有一個三公升的量杯與五公升的量杯，要取出四公升的量的話，我們可以這樣做：

1. 把五公升的量杯裝滿水
2. 把五公升量杯裡的水倒滿三公升的量杯
3. 把三公升裡剩下的水倒掉
4. 把五公升量杯剩下的水全部倒到三公升量杯
5. 把五公升的量杯裝滿水
6. 把五公升量杯裡的水倒滿三公升的量杯

此時五公升的量杯裡就恰好剩下四公升的水了。

如果給你任意的空量杯，你能算出最少要幾個步驟才能得到需要的量嗎?

一個步驟可以做下列事情

• 把一個量杯裝滿水
• 把一個量杯內的水倒掉
• 把一個量杯的水全部倒給或是倒滿另一個量杯

輸入說明

每筆測資點只有一筆測資，佔三行。第一行有一個整數$T$，表示有幾個量杯，第二行有$T$個整數，分別表示每個量杯的容量為何。最後一行有一個整數$Q$，為詢問的容量。

保證

• $1\leq T\leq 5$
• $1\leq 量杯容量\leq 50$
• $1\leq Q\leq 50$

  輸出說明

輸出一行，為最少步數。若無法完成輸出$-1$。

範例輸入

3
5 8 11
2

範例輸出

4

提示

來源

TIOJ 1008

Judge Setting

run-time limit: 300 ms
memory limit: 655360 byte
測資數量: 0