1185: ALGO의 첫 체육관 도전

Memory Limit:64 MB Time Limit:0.500 S
Judge Style:Text Compare Creator:
Submit:7 Solved:5

Description

ALGO는 포켓몬 트레이너로서의 여정을 시작했고, 그의 첫 파트너는 치코리타 입니다.

ALGO와 치코리타는 자신들의 첫 체육관 배지를 얻기 위해 Chang-One시티의 체육관에 도전 하기로 결정했습니다.

체육관 도전 과정에서 ALGO는 치코리타와 함께 다양한 상대 포켓몬과 전투를 벌이게 됩니다.

전투에서 승리할 때마다 치코리타는 경험치(EXP)를 얻게 되며, 특정 경험치를 모두 얻으면 체육관 배지를 획득할 수 있습니다.

이번 도전에서 ALGO와 치코리타는 전투를 통해 정확히 K만큼의 경험치를 얻어야 합니다.

전투마다 얻는 경험치는 다를 수 있으며, ALGO는 치코리타가 필요한 경험치를 정확히 얻을 수 있도록 전투를 선택해야 합니다.


Input

  • 첫 번째 줄에 ALGO와 치코리타가 참여할 수 있는 전투의 수 N(1 ≤ N ≤ 100)이 주어집니다.
  • 두 번째 줄에 N개의 전투에서 치코리타가 얻을 수 있는 경험치가 공백으로 구분되어 주어집니다. 각 전투에서 얻을 수 있는 경험치는 1에서 100 사이의 정수입니다.
  • 세 번째 줄에 ALGO와 치코리타가 목표로 하는 경험치 K가 주어집니다. K의 값은 1에서 10,000 사이의 정수입니다.

Output

ALGO와 치코리타가 정확히 K만큼의 경험치를 얻기 위해 필요한 전투의 최소 횟수를 출력합니다. 만약 K만큼의 경험치를 얻을 수 있는 방법이 없다면, -1을 출력합니다.

Sample Input Copy

3
4 2 6
6

Sample Output Copy

1