Karlo lực sĩ đang ở phòng gym. Có một dãy ~a~ gồm ~n~ số, trong đó mỗi số biểu diễn khối lượng của một món đồ đặt trước mặt Karlo. Ngoài ra còn có một số nguyên ~k~, biểu diễn số loại tạ khác nhau mà Karlo có thể dùng.

Với mỗi loại tạ từ ~1~ tới ~k~, và với từng phần tử trong dãy, Karlo thực hiện các bước sau:

1. Chia khối lượng của món đồ cho loại tạ đang xét và lấy phần nguyên của phép chia.
2. Nhân số nguyên vừa nhận được với khối lượng món đồ sau khi tăng thêm ~2~. Nếu kết quả lớn hơn ~10^8~ thì thay bằng ~10^8~.
3. Cộng tất cả các giá trị thu được cho loại tạ đó. Tổng này được gọi là sức mạnh của loại tạ tương ứng.

Karlo quan tâm tới tổng sức mạnh của tất cả các loại tạ trong phòng gym. Vì cậu ấy không có thời gian tự tính, hãy giúp Karlo.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~: số món đồ đặt trước mặt Karlo và số loại tạ Karlo có thể dùng.

Dòng thứ hai chứa ~n~ số ~a_1, a_2, \ldots, a_n~, là khối lượng của các món đồ.

Output

In ra một số nguyên duy nhất là đáp án của bài toán.

Ràng buộc

• ~1 \le n, k \le 10^5~
• ~1 \le a_i \le 10^5~
• Mỗi giá trị trung gian ở bước ~2~ bị chặn trên bởi ~10^8~

Chấm điểm

• Subtask 1 (17 điểm): ~k \le 300~
• Subtask 2 (19 điểm): Dãy ~a~ có nhiều nhất ~300~ giá trị phân biệt
• Subtask 3 (34 điểm): Không có ràng buộc bổ sung.

Sample Input 1

1 2
2

Sample Output 1

12

Sample Input 2

2 1
3 4

Sample Output 2

39

Sample Input 3

7 19
1 2 3 4 5 6 7

Sample Output 3

414

Giải thích

• Ví dụ 2: Với loại tạ ~1~, số ~3~ được biến đổi thành ~3 \cdot 5 = 15~, còn số ~4~ được biến đổi thành ~4 \cdot 6 = 24~. Tổng hai giá trị này bằng ~39~.