Эта задача идентична задаче «Простая задача о монетах» (Easy), за исключением ограничений на $N$ и $M$.

Куонг живет в королевстве Кёнхи. В королевстве Кёнхи используются $N$ типов монет номиналом $P_1, P_2, \dots, P_N$.

Удивительно, но в королевстве Кёнхи могут существовать монеты с нулевой или отрицательной стоимостью.

Куонг хочет заплатить ровно $M$ вон за покупку товара. Разумеется, если $M$ равно $0$ или отрицательно, он все равно должен заплатить ровно $M$ вон. У Куонга есть бесконечное количество монет каждого типа, поэтому, если существует способ заплатить ровно $M$ вон, он всегда сможет это сделать.

Например, если нужно заплатить $94$ воны монетами номиналом $50$ и $-3$, минимальное количество необходимых монет составляет $4$ (две монеты по $50$ и две монеты по $-3$). Невозможно заплатить ровно $94$ воны меньшим количеством монет.

Входные данные

В первой строке через пробел заданы количество типов монет $N (0 \le N \le 2\,000)$ и сумма, которую нужно заплатить, $M (-10\,000 \le M \le 10\,000)$.

Во второй строке через пробел заданы номиналы каждой монеты $P_1, P_2, \dots, P_N (-1\,000 \le P_i \le 1\,000)$. Если $N = 0$, вторая строка во входных данных отсутствует.

Все входные числа являются целыми.

Выходные данные

Выведите минимальное количество монет, необходимое для оплаты суммы $M$. Если оплатить сумму $M$ невозможно никаким способом, выведите $-1$.

Примеры

Входные данные 1

2 94
50 -3

Выходные данные 1

4

Входные данные 2

2 999
2 4

Выходные данные 2

-1

Входные данные 3

1 -5
-1

Выходные данные 3

5

Входные данные 4

0 1

Выходные данные 4

-1

Входные данные 5

2 0
1 -1

Выходные данные 5

0