Trong phần 1 của chương D, ta đã biết cách chọn quà cho đúng nhất, vậy ở trong phần 2 này, chúng ta sẽ đưa ra cách chọn quà sao cho gây ám ảnh (theo nghĩa đen) cho người ấy nhất của bạn (tất nhiên để bạn tránh và không mắc sai lầm), cách chọn quà ấy như sau:

• Cho một list gồm $n$ món quà với món quà thứ $i$ có giá trị $a_i$, bạn chọn ra một dãy con (tới đây là nó đã đủ khủng khiếp cho người ấy rồi) gồm $k$ phần tử, gọi $p$ là tập hợp gồm $k$ phần tử là vị trí các món quà bạn chọn thì độ khủng khiếp của cách chọn quà là giá trị lớn nhất của bình phương tổng các món quà liên tiếp không được chọn bất kì và bình phương tổng giá trị các món quà được chọn.

Ví dụ, khi cho list $7$ món quà $[1;\ 5;\ 2;\ 6;\ 8;\ 4;\ 3]$ và bạn chọn $2$ món quà thứ $1$ và $5$ thì độ khủng khiếp của cách chọn này là $max({(1 + 8)}^2, {(5 + 2 + 6)}^2, {(3 + 4)}^2) = 13^2 = 169.$

Bạn sẽ được cho một list gồm $n$ món quà và số lượng quà cần chọn là $k$, nhiệm vụ của bạn là tính độ khủng khiếp nhỏ nhất của một cách chọn quà để theo đó mà chọn cho người ấy nhé.

(nếu như bạn thắc mắc vì sao chọn quà mà lại khủng khiếp thì hãy viết ra một dãy số vài nghìn phần tử tặng cho người ấy, xin chân thành cám ơn)

Input

• Dòng đầu tiên gồm hai số nguyên $n$ và $k$ - số món quà trong list và số lượng quà cần chọn. $(1\leq k\leq n\leq 600)$
• Dòng thứ hai là $n$ số nguyên $a_i\ (1\leq i\leq n)$ với $a_i$ là giá trị món quà thứ $i$. $(1\leq a_i\leq 5.10^5)$

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán - độ khủng khiếp nhỏ nhất mà một cách chọn quà có thể đạt được.

Subtasks

• Subtask 1: Đảm bảo $n\leq 16$. (30 điểm)
• Subtask 2: Đảm bảo $n\leq 100$. (70 điểm)
• Subtask 3: Không có ràng buộc gì thêm. (150 điểm)

Example

4 1
1 2 4 6

36