Một vương quốc nọ sử dụng tiền xu với \(N\) mệnh giá khác nhau, lần lượt là \(v_1\), \(v_2\), \(v_3\), ..., \(v_n\) (đồng). Tỉ phú Umbala là một người vô cùng giàu có, đến mức ông ta có đủ vô vàn số lượng tiền xu mỗi mệnh giá.

Sắp tới, Umbala muốn tới thành phố ViFa để mua một chiếc xe ô tô, với giá là \(P\) đồng. Để xếp gọn hành lý, ông ta muốn mang số đồng xu ít nhất có thể, nhưng phải vừa đủ để trả tiền mua xe ô tô - không thừa, không thiếu.

Em hãy viết chương trình tính số đồng xu nhỏ nhất mà Umbala phải mang theo. Nếu không có cách mang theo các đồng xu thoả mãn yêu cầu thì in ra \(-1\).

Input Specification

Gồm ba dòng:

• Dòng thứ nhất chứa số nguyên dương \(N\);
• Dòng thứ hai chứa dãy \(N\) số nguyên dương đôi một khác nhau, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng;
• Dòng thứ ba chứa số nguyên dương \(P\).

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^3\)
• \(v_i \leq 10^4\)
• \(P \leq 10^5\)

Input Sample

3
1 3 5
11

Output Sample

3

Explanation for Sample Output

Umbala có thể mang theo các đồng tiền (1, 5, 5) hoặc (3, 3, 5).