题目描述

Yuzu 喜欢吃糖。

最近 Yuzu 路过了一条商店街。商店街上有 $n$ 家商店排成一排，第 $i$ 家商店售卖一种美味度为 $v_i$ 的糖果。每家商店都有无限的糖果储备，且 Yuzu 可以选择是否在每家商店购买糖果。

Aoi 为了阻止 Yuzu 冲动消费，给 Yuzu 制定了一条规则：Yuzu 只能在第一家商店买最多 $1$ 颗糖果，且她在接下来每一家商店买的糖果数量不能比上一家多超过一颗。具体而言，$[0,1,2,0,1]$ 是符合规则的，而 $[0,0,2,0,0]$ 和 $[0,1,3,0,0]$ 是不符合规则的。

Yuzu 有一个能装下 $m$ 颗糖果的背包。她想知道，在购买不多于 $m$ 颗糖果的情况下，她所购买的糖果的美味度总和最大是多少。

输入格式

第一行两个正整数 $n,m$，代表商店的数量和最多购买糖果的数量。

第二行共 $n$ 个数，第 $i$ 个数为 $v_i$ 的值，代表第 $i$ 家商店售卖糖果的美味度。

输出格式

一行一个整数，代表最大可以获得的美味度总和。

6 6
1 1 4 5 1 4

24

数据范围

• 对于 $30\%$ 的数据，$1 \le n,m \le 10$；
• 对于 $60\%$ 的数据，$1 \le n,m \le 200$；
• 对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$0 \le v_i \le 10^9$。