Miss Sloane

영화에서 냉철한 로비스트 엘리자베스 슬론과 그녀가 일하는 회사에 총기 제조업체 대표 빌 샌퍼드가 접근한다. 샌퍼드는 총기 구매 시 신원 조회를 확대하려는 Heaton-Harris 법안에 반대하는 측을 이끈다. 샌퍼드는 투표할 때 드러나는 여성 유권자의 모성 성향을 뒤집기 위해 여성 유권자를 겨냥하자고 제안한다. 슬론은 이 제안을 비웃었다. 그녀는 의원의 권력이 의원 자신이 아니라 모든 사람에게 이익이 되도록 행사되어야 하며, 그것이 옳은 일이라고 믿었다.

이 문제에서는 반대편 입장을 택한다. 슬론이 샌퍼드의 역할을 맡아 Heaton-Harris 법안을 막는 캠페인을 벌인다. 목표는 상원의원들이 법안에 합의하지 못하도록 로비하는 것이다. 의회에는 $n$명의 상원의원이 있다. 각 상원의원 $i$는 여러 공공 이슈에 대한 일반적인 의견을 나타내는 양의 정수 $a_i$를 가진다. 각 상원의원이 로비에 저항하는 정도는 양의 정수 $e_i$로 나타낸다. 공공 이슈 지표들의 최대공약수가 1이 아니면 상원의원들이 합의에 이르고 법안이 통과한다. 목표는 이를 막는 것이다.

슬론의 로비 능력은 정수 $k$로 나타낸다. 캠페인은 다음과 같이 진행된다. 매 라운드에서 슬론은 상원의원 한 명, 예를 들어 $i$번째 상원의원에게 접근해 그의 공공 이슈 의견 중 원하는 것에 영향을 줄 수 있다. 그 결과 $a_i$를 $k$ 이하의 자연수 약수로 나눌 수 있다. 다만 상원의원들은 경계하므로 슬론은 각 상원의원에게 최대 한 번만 영향을 줄 수 있다. 또한 로비를 받은 상원의원이 늘어날수록 다음 로비에 드는 시간이 길어진다. 슬론이 이미 $x$명의 상원의원을 로비했고 그들의 저항값 합이 $y$라고 하자. 이때 $i$번째 상원의원을 추가로 로비하면 $y + e_i (x + 1)$ 단위의 시간이 걸린다.

캠페인을 완료하는 데 필요한 최소 시간을 구하라. 불가능하면 -1을 출력하라.

첫째 줄에 상원의원 수 $n$과 슬론의 로비 능력 $k$가 주어진다. 둘째 줄에는 상원의원들의 지표 $a_1, a_2, \ldots, a_n$이 주어진다. 셋째 줄에는 상원의원들의 저항값 $e_1, e_2, \ldots, e_n$이 주어진다.

캠페인을 완료하는 데 필요한 최소 시간을 출력한다. 불가능하면 -1을 출력한다.

$1 \le n \le 10^6$

$1 \le k \le 10^{12}$

$1 \le a_i \le 10^{12}$

$1 \le e_i \le 10^9$