在电影中，精明强干的游说者 Elizabeth Sloane 和她所在的事务所被枪支制造代表 Bill Sanford 接洽，后者领导着反对拟议的 Heaton-Harris 法案的阵营，该法案旨在扩大购枪背景调查。Sanford 特别提议针对女性选民，以扭转她们在投票时的母性倾向。Sloane 小姐嘲笑了这个想法，因为她坚信国会议员的权力应该以造福所有人而非仅仅造福议员自身的方式行使，这才是正确的做法。

在本题中，你将扮演另一个场景，即 Sloane 小姐接受了 Bill Sanford 的提议，开展反对 Heaton-Harris 法案的运动。你的目标是以一种能够阻止参议员们就该法案达成一致的方式对他们进行游说！国会中有 $n$ 名参议员，每位参议员都有一个正整数指标 $a_i$，代表其对各种公共议题的总体观点。每位参议员对游说的抵触程度由另一个正整数 $e_i$ 表示。当所有参议员的公共议题指标的最大公约数不为 1 时，参议员们将达成一致，Heaton-Harris 法案的投票将会通过。显然，你的目标是防止这种情况发生。

Sloane 小姐的游说能力由一个整数 $k$ 表示。游说活动进行如下：在每一轮中，Sloane 小姐可以选择接触一位参议员（例如第 $i$ 位参议员），并影响其对 Sloane 小姐所选定的某些公共议题的观点。结果，Sloane 小姐可以将第 $i$ 位参议员的公共议题指标 $a_i$ 除以一个不超过她游说能力 $k$ 的自然数。然而，参议员们并非傻瓜。因此，Sloane 小姐对每位参议员最多只能进行一次影响（无论是通过诱导还是勒索）。此外，随着活动的进行，被游说的参议员越多，进一步诱导（影响）其他参议员所需的时间就会显著增加。如果 Sloane 小姐已经游说了 $x$ 名参议员，且这些参议员的总抵触程度为 $y$，此时她想要进一步游说第 $i$ 位参议员，那么游说第 $i$ 位参议员将需要 $y + e_i \cdot (x + 1)$ 个单位时间来完成。

请计算 Sloane 小姐完成该运动所需的最短时间，如果无法完成，则输出 -1。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示参议员的人数和 Sloane 小姐的游说能力。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示 $n$ 位参议员的指标。 第三行包含 $n$ 个整数 $e_1, e_2, \dots, 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$

样例

样例输入 1

3 6
30 30 30
100 4 5

样例输出 1

18

样例输入 2

1 1000000
1
100

样例输出 2

0

样例输入 3

3 5
7 7 7
1 1 1

样例输出 3

-1