làm c++ hoặc python

Ánh muốn thực hiện một cuộc hành trình xuyên qua các thành phố trên đất nước MTTN. Đất nước MTTN có $n$ thành phố nằm dọc theo tuyến đường sắt chính mình và các thành phố này được đánh số từ $1$ đến $n$.

Ánh lên kế hoạch cho chuyến hành trình của mình như sau. Đầu tiên, cô ấy sẽ chọn một thành phố �1c1​ để bắt đầu cuộc hành trình của mình. Cô ấy sẽ đến thăm thành phố đó và sau đó đi đến một thành phố �2>�1c2​>c1​, sau đó đến một thành phố khác �3>�2,…,c3​>c2​,…, cho đến khi cô chọn kết thúc cuộc hành trình của mình ở thành phố nào đó ��>��−1cm​>cm−1​. Vì vậy, trình tự các thành phố Ánh sẽ ghé thăm là �1,�2,…,��c1​,c2​,…,cm​ thỏa mãn ��>��−1;∀�∈�,2≤�≤�ci​>ci−1​;∀i∈N,2≤i≤m.

Thành phố thứ i có vẻ đẹp là ��bi​. Nếu Ánh đang ở thành phố thứ $i$ thì Ánh chỉ có thể mua được vé tàu đến thành phố thứ $j$ thỏa mãn �>�,�−�=��−��j>i,j−i=bj​−bi​. Tuy nhiên, do Ánh là hành khách nổi tiếng của đất nước MTTN nên Ánh được công ty đường sắt tặng $k$ vé tàu có thể di chuyển từ thành phố $i$ đến bất kỳ thành phố $j>i$ nào.

Ví dụ, nếu $n=9,k=1$ và $b=[1,2,3,4,6,6,8,9]$, Ánh có thể có một số cách có thể lập kế hoạch cho chuyến đi của mình:

• $c=[1,2,3,4]$
• $c=[6,7,8]$
• $c=[1,2,3,4,6,7,8]$

Do đây là lần đầu tiên thực hiện một cuộc hành trình xuyên qua các thành phố trên đất nước MTTN nên Ánh muốn hành trình của mình đẹp nhất có thể. Giá trị vẻ đẹp của hành trình là tổng giá trị vẻ đẹp của tất cả các thành phố đã ghé thăm. Bạn hãy giúp cô ấy tìm ra giá trị vẻ đẹp lớn nhất của cuộc hành trình nhé?

Input

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ (1≤�≤4×105,0≤�≤min(�−1,30))(1≤n≤4×105,0≤k≤min(n−1,30)) --- số lượng thành phố ở đất nước MTTN và số lượng tấm vé đặc biệt mà Ánh có.
• Dòng thứ hai chứa $n$ số nguyên �1,�2,…,��b1​,b2​,…,bn​ (1≤��≤106)(1≤bi​≤106), trong đó ��bi​ là giá trị vẻ đẹp của thành phố thứ $i$.

Output

• In ra một số nguyên duy nhất là giá trị tối đa của vẻ đẹp của cuộc hành trình mà Ánh có thể chọn.

Scoring

• Subtask $1$ ($16\%$ số điểm): $n\le 1000,k=0$.
• Subtask $2$ ($16\%$ số điểm): $n\le 1000,k=1$.
• Subtask $3$ ($18\%$ số điểm): $n\le 1000$.
• Subtask $4$ ($16\%$ số điểm): $k=0$.
• Subtask $5$ ($16\%$ số điểm): $k=1$.
• Subtask $6$ ($18\%$ số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input

8 1 1 2 3 4 6 6 8 9

Output

33