Statement is not available in English language
E2. 간단한 동전 문제 (Hard)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

이 문제는 간단한 동전 문제 (Easy)와 N과 M의 제한을 제외하면 동일한 문제입니다.

쿠옹이는 경희 왕국에 살고 있다. 경희 왕국에서는 P1원, P2원, ..., PN원의 N종류의 동전을 사용한다.

신기하게도 경희 왕국에는 0 또는 음수의 가치를 가지는 동전이 있을 수 있다.

쿠옹이는 물건을 사기 위해 정확히 M원을 지불하려 한다. 물론 M이 0 또는 음수인 경우에도 정확히 M원을 지불해야 한다. 쿠옹이는 각 동전을 무한히 많이 가지고 있어서 정확히 M원을 지불하는 방법이 있다면 항상 지불할 수 있다.

예를 들어 50원 동전과  - 3원 동전으로 94원을 지불해야 한다면 지불해야 하는 동전의 최소 개수는 50원 2개,  - 3원 2개로 총 4개이다. 이보다 적은 개수의 동전으로 정확히 94원을 지불할 수는 없다.

Input

첫째 줄에 동전의 종류 N(0 ≤ N ≤ 2 000)과 지불할 금액 M( - 10 000 ≤ M ≤ 10 000)이 공백으로 구분되어 주어진다.

둘째 줄에 각 동전의 가치 P1, P2, ..., PN ( - 1 000 ≤ Pi ≤ 1 000)가 공백으로 구분되어 주어진다. 만약 N = 0이라면 입력에 둘째 줄은 주어지지 않는다.

입력되는 모든 수는 정수이다.

Output

M원을 지불하기 위해 필요한 동전의 최소 개수를 출력하라. 어떤 방법으로도 M원을 지불할 수 없다면  - 1을 대신 출력하라.

Examples
Input
2 94
50 -3
Output
4
Input
2 999
2 4
Output
-1
Input
1 -5
-1
Output
5
Input
0 1
Output
-1
Input
2 0
1 -1
Output
0