World Tour by Air – Minimizing Flight Costs

A famous movie once showed an 80‐person gang traveling the world in 80 days. In this problem a (possibly smaller) group of M travelers wishes to do just that – but only flying westward. The countries are numbered 1 through N from east to west. Each traveler’s itinerary is a (possibly empty) strictly increasing sequence of country numbers where they disembark (i.e. make a landing). When a traveler lands in a country they are said to have visited that country. Note that if a traveler lands in some country i, then, because they only travel westward, they must have landed in all previous countries in their itinerary. In other words, if a traveler’s landing countries are P₁, P₂, …, P_k (with 0 ≤ k ≤ N), then it must hold that P₁ < P₂ < … < P_k.

Each country i has an attractiveness value V_i (a positive integer). This value means that exactly V_i travelers must visit country i. (Note that since every traveler who travels must first visit country 1, it is necessary that V₁ = M.) It is not hard to see that in order for an assignment of itineraries to exist, the attractiveness values must be monotone nonincreasing (i.e. V₁ ≥ V₂ ≥ … ≥ V_N).

All travel is by airplane. When a traveler buys a flight ticket from country i (or the starting point 0) to country j (with j > i) the ticket cost is given by the square of the distance, that is, (j - i)². Each traveler who actually makes a stop pays the cost for that leg of their journey. If a traveler’s itinerary is P₁, P₂, …, P_k, then their total cost is

Since the square function is convex, it is always cheaper to break a long flight into several shorter ones. Thus if it is possible to choose the itineraries so that every traveler makes as many stops as possible the total cost will be minimized. In fact, under the constraint that exactly V_i travelers visit country i, it turns out that the optimal strategy is to have every traveler make every possible stop. (That is, if a traveler goes as far as country r, then their itinerary will be 1, 2, …, r.)

Under this strategy the number of travelers landing in country i is V_i - V_i+1 (where we define V_N+1 = 0). Consequently, the total minimum cost is

[ \text{Total Cost} = 1V_1 + 1V_2 + \cdots + 1*V_N = \sum_{i=1}^{N} V_i. ]

Your task is very simple: Given N, M and the attractiveness values V₁, V₂, …, V_N (which satisfy V₁ = M and are nonincreasing), compute the minimum total flight cost.

Note: It can be shown that under the feasibility condition the optimal itineraries are unique – every traveler who goes as far as country r will stop in every country from 1 to r – and the minimum total cost is exactly \(\sum_{i=1}^{N} V_i\).

inputFormat

The input consists of two lines:

• The first line contains two integers N and M (1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵), where M is the number of travelers and N the number of countries.
• The second line contains N positive integers V₁, V₂, …, V_N (each ≤ 10⁹), representing the attractiveness of each country. It is guaranteed that V₁ = M and that V₁ ≥ V₂ ≥ … ≥ V_N.

outputFormat

Output a single integer – the minimum possible total flight cost.

sample

3 3
3 2 1

6