Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Слой профессионалов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кардблаф - популярный вид спорта в Телеграме. Каждый игрок в Кардблаф когда-либо мечтал попасть в слой профессионалов. В слое профессионалов сейчас $$$n$$$ судей и вы проходите туда отбор. У вас есть число $$$k$$$ — ваше умение играть в Кардблаф.

Каждый судья имеет число $$$a_i$$$ — показатель неуверенности относительно того, брать вас или нет, а также опыт $$$e_i$$$. Для того, чтобы убеждать судей, вам нужно играть с ними. С каждым судьёй вы можете сыграть только один раз. По результатам игры вы можете уменьшить неуверенность $$$i$$$-го судьи, разделив её на любой делитель $$$a_i$$$ небольший $$$k$$$. Если НОД всех показателей судей будет равен $$$1$$$, то они придут к согласию и возьмут вас в слой профессионалов.

Также вы хотели бы минимизировать время, потраченное на убеждение судей. Известно, что если вы сыграете с $$$x$$$ судьями с суммарным опытом $$$y$$$, то потратите $$$x \cdot y$$$ секунд.

Выведите минимальное время для вступление в слой профессионалов, если это возможно, и $$$-1$$$, иначе.

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

В первой строке содержатся два числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq k \leq 10^{12}$$$) — число судей и ваше умение играть в Кардблаф.

Во второй строке содержатся $$$n$$$ чисел, где $$$i$$$-е число $$$a_i$$$ ($$$1 \leq a_i \leq 10^{12}$$$) — неуверенность $$$i$$$-го судьи.

В третьей строке содержатся $$$n$$$ чисел в аналогичном формате ($$$1 \leq e_i \leq 10^9$$$), $$$e_i$$$ — опыт $$$i$$$-го судьи.

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

Выведите одно число - минимальное число секунд, если существует способ убедить судей, и $$$-1$$$, иначе.

Примеры
Входные данные
3 6
30 30 30
100 4 5
Выходные данные
18
Входные данные
1 1000000
1
100
Выходные данные
0
Входные данные
3 5
7 7 7
1 1 1
Выходные данные
-1