Кардблаф - популярный вид спорта в Телеграме. Каждый игрок в Кардблаф когда-либо мечтал попасть в слой профессионалов. В слое профессионалов сейчас \(n\) судей и вы проходите туда отбор. У вас есть число \(k\) — ваше умение играть в Кардблаф.
Каждый судья имеет число \(a_i\) — показатель неуверенности относительно того, брать вас или нет, а также опыт \(e_i\). Для того, чтобы убеждать судей, вам нужно играть с ними. С каждым судьёй вы можете сыграть только один раз. По результатам игры вы можете уменьшить неуверенность \(i\)-го судьи, разделив её на любой делитель \(a_i\) небольший \(k\). Если НОД всех показателей судей будет равен \(1\), то они придут к согласию и возьмут вас в слой профессионалов.
Также вы хотели бы минимизировать время, потраченное на убеждение судей. Известно, что если вы сыграете с \(x\) судьями с суммарным опытом \(y\), то потратите \(x \cdot y\) секунд.
Выведите минимальное время для вступление в слой профессионалов, если это возможно, и \(-1\), иначе.
Выходные данные
Выведите одно число - минимальное число секунд, если существует способ убедить судей, и \(-1\), иначе.