33943번 - 간단한 동전 문제 (Hard)

문제

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

쿠옹이는 경희 왕국에 살고 있다. 경희 왕국에서는 $P_1$원, $P_2$원, $\cdots,ドル $P_N$원의 $N$종류의 동전을 사용한다.

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

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

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

입력

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

둘째 줄에 각 동전의 가치 $P_1,ドル $P_2,ドル $\cdots,ドル $P_N$ $(-1,000円 \le P_i \le 1,000円)$가 공백으로 구분되어 주어진다. 만약 $N = 0$이라면 입력에 둘째 줄은 주어지지 않는다.

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

출력

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

제한

힌트