Hôm nay là sinh nhật ~wanwan~ tròn ~18~ tuổi. Mẹ mua tặng ~wanwan~ một chiếc bánh kem dâu tây rất to.

Bánh kem có độ ngọt là ~x~, trên bánh kem có ~n~ quả dâu tây, quả thứ ~i~ có độ ngọt là ~a_i~.

Là một fan cuồng của đồ ngọt, ~wanwan~ rất muốn thưởng thức bánh kem dâu tây kèm với sữa TH True Milk. Thế nhưng tùy vào quả dâu tây và độ ngọt của bánh mà sữa sẽ có vị ngọt khác nhau. Độ ngọt của sữa khi ăn quả dâu tây thứ ~i~ kèm bánh là tổng các bội của ~a_i~ mà bé hơn ~x~.

Tính tổng độ ngọt của sữa khi ~wanwan~ ăn hết ~n~ quả dâu tây.

Lưu ý: Tổng độ ngọt luôn được đảm bảo không vượt quá ~2^{64}~

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n, x~ lần lượt là số lượng dâu tây trên bánh kem và độ ngọt của bánh. ~(1 \le n \le 10^5, 1 \le x \le 10^{9})~
• Dòng thứ ~2~ chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ là độ ngọt của ~n~ quả dâu tây. ~(1 \le a_i \le 10^{8})~

Output

• In ra số nguyên duy nhất là tổng độ ngọt của sữa khi ~wanwan~ ăn hết ~n~ quả dâu tây.

Sample Input

3 20
5 10 7

Sample Output

61

Note

• Độ ngọt của sữa khi ~wanwan~ ăn quả dâu tây thứ nhất là ~5 + 10 + 15 = 30~
• Độ ngọt của sữa khi ~wanwan~ ăn quả dâu tây thứ hai là ~10~
• Độ ngọt của sữa khi ~wanwan~ ăn quả dâu tây thứ ba là ~7 + 14 = 21~
• Tổng độ ngọt sau khi ăn ba quả dâu tây là ~30 + 10 + 21 = 61~

Subtask

• ~50\%~ số test có ~1 \le n \le 10^3~, ~1 \le a_i, x \le 10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm

~Chovang~ một cậu học sinh rất đam mê Toán học, cậu rất hay nghĩ ra những bài toán hay để thách đố mọi người. Hôm nay, cậu được học về bội chung nhỏ nhất, nên cậu đã nghĩ ra một bài toán như sau:

• Tìm ~x, y~ sao cho ~LCM(LCM(x, y), a) = T~ ~(x,y \neq 1~ và ~x,y \neq T)~, với ~LCM~ là kí hiệu của bội chung nhỏ nhất, ~a~ và ~T~ cho trước.

Bạn hãy giải bài toán mà ~Chovang~ đưa ra nhé!

Input

• Một dòng duy nhất chứa ~2~ số nguyên ~a~ và ~T~ ~(1 \leq a, T \le 10^9)~

Output

• In ra ~2~ số ~x~ và ~y~. Nếu không có cặp số ~x, y~ nào thoả mãn, in ra ~-1~

Sample Input 1

6 144

Sample Output 1

9 16

Sample Input 2

6 10

Sample Output 2

-1

Note

• Ở test mẫu ~1~, ta có ~LCM(9, 16) = 144~.
• Ở test mẫu ~2~, ta không thể tìm được cặp số ~x, y~ nào thoả mãn.

Subtask

• ~50\%~ số test có ~a, T \le 100~
• ~50\%~ số test còn lại không có giới hạn gì thêm.

Trong mọi cuộc chiến, có thể nói phần hậu cần lúc nào cũng là phần quan trọng nhất. Một đoàn quân lương nọ có ~n~ giá trị quân lương bị đột kích và phải bỏ lại một phần quân lương trong đoạn [~L~, ~H~] (với ~a_L, a_{L+1}, … a_R~ và ~1~ < ~L \le H~ < ~n~) để số quân lương còn lại chạy thoát. Biết rằng số quân lương còn lại phải có trung bình cộng nhỏ nhất có thể. Hãy tính giá trị trung bình cộng nhỏ nhất đó.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~3 \leq n \le 10 ^ 5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, … a_n~. (~1 \leq a_i \le 10 ^ 4~).

Output

• Ghi ra giá trị trung bình cộng nhỏ nhất của số quân lương còn lại. Hãy in chính xác ~3~ chữ số thập phân đằng sau dấu phẩy.

Sample Input

3
2 1 2

Sample Output

2.000

Note

Xóa đoạn [~2~, ~2~] (xóa số ~1~), số quân lương còn lại là ~2~, ~2~. Có trung bình cộng là (~2~+~2~)/~2~ = ~2.000~

Subtask

• ~20\%~ số test có ~n \le 100~
• ~30\%~ số test tiếp theo có ~n \le 1000~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Trong thành phố ~Bedao~, các nhà khoa học đã tìm thấy được ~N~ viên đá phát sáng, mỗi viên được phân biệt dựa trên ~K~ tính chất của viên đá đó. Người ta định nghĩa sự giống nhau giữa viên đá ~A~ và ~B~ bằng phép XNOR được thể hiện qua bảng dưới đây:

Các nhà khoa học muốn tạo ra một viên đá mới sao cho sự giống nhau lớn nhất giữa viên đá mới và ~N~ viên đá đã được tìm thấy là bé nhất.

Input

• Dòng đầu tiên gồm hai số ~N~, ~K~ lần lượt là số lượng viên đá phát sáng và số tính chất của tất cả các viên đá đó ~(1 \le N \le 10^5, 1 \le K \le 20)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa một dãy nhị phân biểu diễn tính chất của viên đá đó

Output

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

Sample Input

3 6
110111
011000
111110

Sample Output

3

Note

• Giả sử viên đá mới có tính chất là ~110001~, kết quả sẽ là ~max(4, 3, 2) = 4~
• Nhưng nếu viên đá mới có tính chất là ~100000~ thì kết quả sẽ là ~max(2, 3, 2) = 3~.
• Như vậy kết quả của ví dụ trên sẽ là ~3~ và ta có thể chứng minh nó là đáp án tối ưu nhất.

Subtask

• ~30\%~ số test có ~N \le 10~
• ~30\%~ số test tiếp theo có ~N \le 10^3~
• ~40\%~ số test còn lại không có điều kiện gì thêm.

CTH cần xây một bức tường từ các khối đá hình lập phương với kích thước ~1 \times 1 \times 1~. Bức tường gồm nhiều cột xếp cạnh nhau, mỗi cột được tạo thành bằng cách xếp chồng các khối đá. Các cột tạo thành bức tường có thể có độ cao khác nhau, độ cao của một cột là số khối đá tạo nên cột đó. CTH muốn xây một bức tường có đúng ~n~ cột đánh số lần lượt từ ~1~ tới ~n~, cột thứ ~i~ có độ cao ~a_i~.

CTH chế tạo một con robot xây tường, để robot hoạt động theo ý muốn cần truyền vào ~2~ dãy số có cùng độ dài ~H~ (~H~ là số nguyên không âm bất kỳ):

• Dãy ~L~: ~L_1, L_2, L_3, ..., L_H~
• Dãy ~R~: ~R_1, R_2, R_3, ..., R_H~
• ~1 \leq L_i \leq R_i \leq n~ với mọi ~1 \leq i \leq H~

Robot thực hiện ~H~ bước, tại bước thứ ~i~, robot thả các khối đá từ độ cao ~i~ xuống các cột có chỉ số thuộc đoạn ~[L_i, R_i]~. Tuy nhiên robot lại rất vụng về nên khối đá chỉ có thể xếp lên tường một cách hoàn hảo nếu như ngay dưới nó (tức ở độ cao ~i-1~) là mặt đất hoặc là một khối đá khác (coi độ cao của mặt đất là ~0~). Tất cả những trường hợp còn lại, khối đá sẽ rơi xuống và bị vỡ ngay lập tức.

Dễ thấy con robot khá phế vì có một số bức tường có dạng đặc biệt không thể nào chỉ dùng robot mà xây hoàn chỉnh được, vì vậy CTH có thể phải đi sửa chữa lại một tí để bức tường đúng ý mình. Cụ thể, với những cột đá cao hơn mong muốn, CTH sẽ phải leo lên lấy khối đá trên cùng của cột đó xuống, số bậc thang phải leo là ~2~ lần độ cao của cột trước khi lấy khối đá xuống. Còn với những cột đá thấp hơn mong muốn, anh phải ôm ~1~ khối đá leo lên để đặt nó lên trên, số bậc thang phải leo là ~2~ lần độ cao của cột sau khi đặt khối đá mới lên.

Cho thông tin về bức tường CTH muốn xây, hãy giúp CTH điều khiển con robot sao cho tổng số bậc thang phải leo để hoàn thành bức tường là ít nhất có thể.

Lưu ý: Sau khi robot hoàn thành ~H~ bước xây, CTH mới bắt đầu leo lên để chỉnh sửa theo ý muốn của mình.

Input

• Dòng đầu tiên cho số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~
• Dòng thứ hai chứa dãy gồm ~n~ số nguyên không âm ~a_1, a_2, a_3, ..., a_n~ mô tả bức tường mong muốn của CTH ~(a_i \leq 10^6)~

Output

• In ra ~1~ số nguyên duy nhất là số bậc thang ít nhất cần phải leo để hoàn thành bức tường.

Sample Input 1

5
9 0 9 0 9

Sample Output 1

180

Sample Input 2

3
2 1 3

Sample Output 2

4

Note

Sample 1

CTH chọn:

• ~H = 9~
• ~L = \{1, 1, 1, 1, 1, 1, 1, 1, 1\}~
• ~R = \{5, 5, 5, 5, 5, 5, 5, 5, 5\}~

Sau khi robot hoàn thành, độ cao của các cột đều là ~9~.

Đối với cột thứ ~2~ và cột thứ ~4~, tại mỗi cột CTH mất ~18~ lần leo thang để lấy khối đá trên cùng xuống, ~16~ lần để lấy khối tiếp theo, ~14~ lần cho khối tiếp theo nữa,..., ~2~ lần cho khối đá dưới cùng. Tổng cộng là ~90~ lần leo cho mỗi cột.

Có thể chứng minh được đây là phương án tối ưu.

Sample 2

CTH chọn:

• ~H = 3~
• ~L = \{1, 3, 2\}~
• ~R = \{3, 3, 3\}~

Quy trình xây tường của Robot như sau:

• Sau bước thứ nhất, độ cao của các cột lần lượt là: ~{1, 1, 1}~.
• Sau bước thứ hai, độ cao của các cột lần lượt là: ~{1, 1, 2}~.
• Sau bước thứ ba, độ cao của các cột lần lượt là: ~{1, 1, 3}~. Lưu ý, tại bước này robot có thả ~1~ khối đá xuống cột thứ ~2~, nhưng vì trước đó cột ~2~ có độ cao là ~1~ mà khối đá lại được thả từ độ cao ~3~ nên nó đã rơi xuống và vỡ.

Sau khi robot thực hiện xong phần việc của nó, CTH cần đặt thêm ~1~ khối đá lên trên cột ~1~, số lần leo cần thiết là ~4~. Dễ thấy, không có phương án nào tối ưu hơn.

Subtask

• ~20\%~ số test có ~n, a_i \le 10^3~
• ~40\%~ số test tiếp theo có ~n \le 10^3~
• ~40\%~ số test còn lại không có điều kiện gì thêm