Waterme1on works in a financial institute as an intern. His job is to help making market prediction. The first exercise from his mentor is to learn when to buy and sell a stock to maximize the profit.

Consider the historical stock prices of n-consecutive days of a stock, where the days are numbered 1, 2, ... , n. Let p[i] be the price of each share of the stock on i-th day . Given an integer k, Waterme1on wants to find exactly k pairs of days (a₁, b₁), (a₂, b₂), ... , (a_k, b_k) where 1 ≤ a₁ < b₁ < a₂ < b₂ < ... < a_k < b_k ≤ n.

For each pair (a_i, b_i) denotes that on day a_i Waterme1on would buy one stock and sell it on day b_i. Because of some magic reasons, Waterme1on would gain profit (p[a_i] - p[b_i])² dollars. Thus, the profit would be simply .

Given the historical stock prices and k, could you help Waterme1on to find exactly k pairs of days to maximize the profit?

西瓜在一個金融公司當實習生，他的工作是利用市場預測來賺大錢。如今，他面臨了他人生第一個大挑戰：透過買賣商品來獲利。

現在西瓜獲得了一個商品在連續 n 天的價格趨勢圖，我們以 p[i] 表示此商品第 i 天的價格。現在給定 k，西瓜想要找恰好 k 個數對 (a₁, b₁), (a₂, b₂), ... , (a_k, b_k)，並且，這 k 個數對滿足 1 ≤ a₁ < b₁ < a₂ < b₂ < ... < a_k < b_k ≤ n。

一個數對 (a_i, b_i) 表示西瓜會在 a_i 天買入此商品，並且在 b_i 天賣出，因為一些神秘原因，西瓜將會在此獲利 (p[a_i] - p[b_i])² 元，因此我們可以將總獲利簡單的表示成 。

現在給定價格趨勢圖與 k，請你幫助西瓜找出他所能獲得的最大獲利。