간단한 동전 문제 (Hard)

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

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

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

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

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

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

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