Sau khi dạo chơi một vòng các nước và tìm hiểu về các sự tích, Heo quyết định quay về vì đã bước vào năm học mới. Tuy nhiên, cậu vẫn đang trên mây sau chuyến hành trình vừa rồi nên cậu quyết định đi kể cho các bạn của mình về chuyến đi vừa rồi.

Trong đất nước nơi Heo sống, chuồng nhà của Heo ở thành phố được đánh số ~1~, ~n - 1~ thành phố còn lại được đánh dấu trên bản đồ là thành phố nơi bạn của Heo sống. Heo và các bạn đã thống nhất với nhau để tạo ra một dãy số thần kì ~a~ gồm có ~n~ phần tử (nhấn mạnh đây không phải quà sinh nhật như mấy cái đề nào đó). Để đi từ nhà thứ ~i~ sang nhà thứ ~i + 1~, Heo có thể mở chuyến bay sử dụng chuyên cơ riêng và tốn cố định E năng lượng. Tuy nhiên, với sức mạnh thần kì của dãy số ~a~ bên trên, Heo có thể kích hoạt cổng dịch chuyển tức thời từ vị trí ~i~ đến vị trí ~j~ ~(i < j)~ nếu ~GCD(a_{i}, a_{i + 1}, ..., a_{j})~ ~=~ ~min(a_{i}, a_{i + 1}, ..., a_{j})~ và tốn ~GCD(a_{i}, a_{i + 1}, ..., a_{j})~ năng lượng. Tất nhiên mọi đường đi đều là hai chiều và Heo chỉ tốn năng lượng khi kích hoạt, còn lúc sử dụng thì chỉ việc chill, không tốn năng lượng. Heo muốn kể chuyện cho mọi người bạn của mình nên các bạn hãy giúp Heo xác định năng lượng tối thiểu để Heo có thể đi đến tất cả nhà của bạn mình và trở thành Tourist chính hiệu thay vì chỉ có cái màu.

Input

Vào từ file văn bản BAI5.inp:

• Dòng đầu là số nguyên ~\aleph~ cho biết chỉ số của subtask ~(1 \le \aleph \le 5)~.

• Dòng thứ hai chứa 2 số nguyên dương ~n~ và ~E~ cho biết số lượng thành phố và năng lượng cần để thiết lập chuyến bay bằng chuyên cơ riêng ~(2 \le n \le 10^{6}~, ~1 \le E \le 10^{9})~.

• Dòng thứ ba chứa dãy số thần kì gồm ~n~ số nguyên ~a_{1}, a_{2}, ..., a_{n}~ ~(1 \le a_{i} \le 10^{9})~.

Output

Ghi ra file văn bản BAI5.out:

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Example

Sample Input 1

1
5 7
15 2 6 15 8

Sample Output 1

23

Sample Input 2

5
2 1000000000
1000000000 1000000000

Sample Output 2

1000000000

Sample Input 3

5
2 1000000000
5 5

Sample Output 3

5

Sample Input 4

5
2 1000000000
4 7

Sample Output 4

1000000000

Sample Input 5

5
2 99999999
1000000000 1000000000

Sample Output 5

99999999