题目描述

薯条哥现在有一批长度不同的木材$woods$，现在需要将木材进行拼接，正好达到总长度$n$,在不考虑切割木材，并且每种长度的木材不限量供应情况下，输出满足要求的最少木材数量，如果无法通过组合达到规定长度，则输出$-1$。

输入描述

第一行输入一个整数$m(1\le m\le 100)$，表示木材的种类数。

第二行输入$m$个整数$woods_1,woods_2,...woods_n(1\le woods_i\le 10^3)$，表示每种木材的长度。

第三行输入一个整数$n(1\le n\le 10^4)$，表示需要达到的总长度。

输出描述

输出满足要求的最少木材数量，如果无法通过组合达到规定长度，输出$-1$

样例

输入

4
1 2 3 5
9

输出

3