“Ta là một nhà giả kim huyền thoại. Chắc chắn ta sẽ tạo ra được thuốc thần Elixir giúp trường sinh bất lão trong truyền thuyết. Khà khà khà!!” – Canuc80k lẩm bẩm khi vừa mở tựa game Clash of Clans lên, vừa thu hoạch đầy bình dầu tím. Tuy nhiên, trên hành trình tạo ra Elixir, Canuc80k đã gặp phải vấn đề sau: trong cửa tiệm giả kim đang bày bán sẵn \(M\) loại nguyên liệu, mỗi loại có chỉ số năng lượng là \(A[i]\). Chỉ số năng lượng của tất cả nguyên liệu là đôi một khác nhau. Do ngân sách có hạn, Canuc80k chỉ được phép mua đúng \(N\) nguyên liệu bất kỳ trong số đó.

Việc pha chế khá phức tạp. Để tạo ra Elixir, Canuc80k cần \(K\) đơn vị Tinh dầu. Để tạo ra một đơn vị Tinh dầu, Canuc80k phải trộn hai nguyên liệu lại với nhau. Giả sử anh ấy trộn hai nguyên liệu có chỉ số năng lượng là \(X\) và \(Y\), quá trình phản ứng sẽ:

• Tạo ra một đơn vị Tinh dầu.
• Đồng thời, phản ứng sinh ra một nguyên liệu mới (phần cặn) có chỉ số năng lượng là \(\text{gcd}(X, Y)\) (Ký hiệu \(\text{gcd}(X, Y)\) là ước chung lớn nhất của \(X\) và \(Y\)). Nguyên liệu mới sinh ra này hoàn toàn có thể được dùng tiếp cho những lần pha chế sau đó.
• Hai nguyên liệu gốc ban đầu (\(X\) và \(Y\)) sẽ biến mất sau phản ứng.

Mục tiêu của Canuc80k là tạo ra đủ \(K\) đơn vị Tinh dầu. Đồng thời, anh ấy muốn sau khi hoàn thành công việc, tổng chỉ số năng lượng của tất cả các nguyên liệu còn lại đạt giá trị lớn nhất.

Yêu cầu: Hãy giúp Canuc80k chọn mua \(N\) nguyên liệu ban đầu và đưa ra phương án pha chế sao cho tổng năng lượng của các nguyên liệu còn sót lại là tối đa.

Input

• Dòng đầu tiên chứa ba số nguyên \(M, N, K\) (\(1 \le K < N \le M \le 5 \cdot 10^6\)) — lần lượt là số lượng nguyên liệu có trong tiệm, số lượng nguyên liệu Canuc80k được mua, và số đơn vị Tinh dầu anh ấy cần tạo ra.
• Dòng tiếp theo chứa \(M\) số nguyên \(A[1], A[2], \dots, A[M]\) (\(1 \le A[i] \le 5 \cdot 10^6\)). Đây là chỉ số năng lượng của các nguyên liệu trong tiệm. Dữ liệu đảm bảo tất cả các số này là phân biệt.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất có thể của các nguyên liệu còn lại sau khi đã tạo đủ \(K\) đơn vị Tinh dầu.

Example

8 6 2
14 13 12 11 2 4 8 9

42

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(M \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(M \le 20\).
• Subtask \(3\) (\(35\%\) số điểm): \(M, A[i] \le 10^5\) và \(M = N\).
• Subtask \(4\) (\(20\%\) số điểm): \(M, A[i] \le 10^5\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.