E - 研究グループの編成 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は大学の研究室の幹事として、 N 人の学生を研究グループに分ける作業を担当しています。学生には 1 から N までの番号が付けられています。

各学生 i には「専門スコア」 W_i が設定されています。 2 人の学生 i , j （ i \neq j ）は、 \gcd(W_i, W_j) \geq K であるとき、かつそのときに限り「協力可能」であると定めます。ここで \gcd は最大公約数を表します。

研究グループの編成は、以下のルールに従わなければなりません。

  • 同じグループに属する任意の 2 人の学生は、直接または間接的に「協力可能」な関係で繋がっていなければならない。具体的には、同じグループに属する任意の 2 人の学生 a , b に対し、学生の列 a = p_1, p_2, \ldots, p_m = b が存在して、隣り合う p_k と p_{k+1} がすべて「協力可能」なペアでなければならない。
  • 逆に、直接または間接的に「協力可能」な関係で繋がっている学生は、必ず同じグループに所属しなければならない。

つまり、各グループに所属する学生の集合は、「協力可能」の関係によって定まる連結成分と一致します。

高橋君は、各グループに所属する学生の専門スコアの合計をそのグループの「総合力」と呼んでいます。すべてのグループのうち、総合力が最大であるグループの総合力を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^6
  • 1 \leq W_i \leq 10^6
  • 入力はすべて整数である

入力

N K
W_1 W_2 \ldots W_N
  • 1 行目には、学生の人数を表す N と、協力可能の基準値を表す K が、スペース区切りで与えられる。
  • 2 行目には、各学生の専門スコアを表す W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。

出力

すべてのグループの総合力の最大値を 1 行で出力せよ。

入力例 1

6 3
6 10 15 7 22 25

出力例 1

56

入力例 2

4 10
2 3 5 7

出力例 2

7

入力例 3

18 6
12 18 25 35 49 77 22 33 55 65 91 14 26 39 52 64 96 160

出力例 3

558

入力例 4

50 50000
100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 99991 199982 299973 399964 499955 599946 699937 799928 899919 999910 65536 131072 196608 262144 327680 393216 458752 524288 589824 655360 70001 140002 210003 280004 350005 420006 490007 560008 630009 700010 1 2 3 49999 50021 75011 99989 123457 234567 345679

出力例 4

5500000

入力例 5

1 1000000
1

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is in charge of dividing N students into research groups as the coordinator of a university laboratory. The students are numbered from 1 to N.

Each student i has a "specialization score" W_i. Two students i and j (i \neq j) are defined to be "compatible" if and only if \gcd(W_i, W_j) \geq K. Here, \gcd denotes the greatest common divisor.

The formation of the research groups must follow these rules:

  • Any two students belonging to the same group must be directly or indirectly connected through "compatible" relationships. Specifically, for any two students a and b in the same group, there must exist a sequence of students a = p_1, p_2, \ldots, p_m = b such that all adjacent pairs p_k and p_{k+1} are "compatible" pairs.
  • Conversely, students who are directly or indirectly connected through "compatible" relationships must belong to the same group.

In other words, the set of students in each group corresponds to a connected component determined by the "compatible" relationship.

Takahashi calls the sum of the specialization scores of the students in each group the "total strength" of that group. Find the maximum total strength among all groups.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^6
  • 1 \leq W_i \leq 10^6
  • All input values are integers.

Input

N K
W_1 W_2 \ldots W_N
  • The first line contains N, the number of students, and K, the threshold for compatibility, separated by a space.
  • The second line contains W_1, W_2, \ldots, W_N, representing the specialization scores of the students, separated by spaces.

Output

Print the maximum total strength among all groups in a single line.

Sample Input 1

6 3
6 10 15 7 22 25

Sample Output 1

56

Sample Input 2

4 10
2 3 5 7

Sample Output 2

7

Sample Input 3

18 6
12 18 25 35 49 77 22 33 55 65 91 14 26 39 52 64 96 160

Sample Output 3

558

Sample Input 4

50 50000
100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 99991 199982 299973 399964 499955 599946 699937 799928 899919 999910 65536 131072 196608 262144 327680 393216 458752 524288 589824 655360 70001 140002 210003 280004 350005 420006 490007 560008 630009 700010 1 2 3 49999 50021 75011 99989 123457 234567 345679

Sample Output 4

5500000

Sample Input 5

1 1000000
1

Sample Output 5

1