Là một cậu học sinh vùi mình trong môn Toán mà lỡ lãng quên mất vẻ đẹp của Văn học, Phúc đang chìm trong sự đau khổ của deadline bài tập làm văn cần phải nộp vào ngày hôm sau. May mắn thay, trước khi cô giáo giao bài tập cô đã gợi ý một số câu trích dẫn hay, và Phúc quyết định sẽ viết tất cả các câu trích dẫn ấy để bài văn của mình có thể gây ấn tượng mạnh với cô.

Cụ thể hơn, cô giáo đã giới thiệu với lớp mình về ~n~ câu trích dẫn hay, và Phúc sẽ viết ra các câu trích dẫn ấy theo đúng thứ tự cô đưa ra trong bài văn của mình. Bằng khả năng cảm thụ văn chương của mình, Phúc đã cảm nhận và đánh giá mỗi câu trích dẫn đều có giá trị nhân sinh nhất định, trong đó câu trích dẫn thứ ~i~ có giá trị nhân sinh là ~a_i~.

Bài văn của Phúc cần phải được bài trí thành nhiều đoạn văn, trong đó mỗi đoạn văn gồm các câu văn liên tiếp. Phúc nhận thấy việc bố trí các câu trích dẫn vào đoạn văn nào là vô cùng quan trọng, bởi theo Phúc mọi đoạn văn đều được đặc trưng bởi giá trị ngưng kết là giá trị nhân sinh lớn nhất trong số các câu trích dẫn của đoạn văn đó. Để bài văn của Phúc được hay, mỗi đoạn văn của Phúc đều phải có ít nhất ~1~ câu trích dẫn, khi đó giá trị lắng đọng của bài văn của Phúc sẽ là ước chung lớn nhất của tất cả các giá trị ngưng kết của các đoạn văn.

Một bài văn của Phúc chỉ hoàn chỉnh khi nó có đúng ~k~ đoạn văn, và bài văn của Phúc có giá trị ngưng kết càng lớn thì bài văn của Phúc sẽ càng hay và dễ đạt điểm cao từ cô hơn.

Các bạn hãy giúp Phúc hoàn thành deadline và thể hiện khả năng văn chương lai láng nhé!

Input

Dòng đầu tiên gồm 2 số nguyên dương ~n, k~ ~(1 \le k \le n \le 10^5)~ - số lượng câu trích dẫn mà cô giáo đã giới thiệu cho lớp và số đoạn văn Phúc dự tính sẽ chia ra trong bài văn của mình.

Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2,..., a_n~ ~(1 \le a_i \le 10^6~, ~\forall i \in [1, n])~ - giá trị nhân sinh của từng câu trích dẫn.

Output

Gồm ~1~ số nguyên dương duy nhất là giá trị lắng đọng lớn nhất mà bài văn của Phúc có thể đạt được.

Scoring

Subtask ~1~ ~(10\%)~: ~1 \le k \le n \le 10^2~, ~1 \le a_i \le 10^6~

Subtask ~2~ ~(15\%)~: ~1 \le k \le n \le 3 \cdot 10^3~, ~1 \le a_i \le 10^6~

Subtask ~3~ ~(25\%)~: ~1 \le k \le n \le 10^5~, ~1 \le a_i \le 2 \cdot 10^2~

Subtask ~4~ ~(50\%)~: ~1 \le k \le n \le 10^5~, ~1 \le a_i \le 10^6~

Sample Input 1

5 2
7 35 13 19 14

Sample Output 1

7