题目描述

小A老师带领 $N$ 名同学郊游至河边，河边有船但无船夫，小A老师曾参加龙舟队，决定亲自划船送同学们过河。小A老师独自划船到对岸需 $T$ 分钟；每多载1名同学，额外增加 $X_1$ 分钟，载 $i$ 名同学时，总共需 $T + X_1 + X_2 + \cdots + X_i$ 分钟。小A老师可将同学分批次摆渡，若中途返回接下一批同学，返回也需 $T$ 分钟，最后一批同学过河后无需返回。求小A老师把所有同学都送到河对岸的最少用时。

输入格式

• 第一行：输入两个整数 $N$ 和 $T$ ，分别表示同学数量和小A老师独自过河所需时间。
• 接下来 $N$ 行：每行输入一个整数 $X_i$ ，表示载 $i$ 名同学时相比载 $i - 1$ 名同学额外增加的时间。

数据范围：对于 $30\%$ 的数据，$1 \leq N \leq 20$ ；对于 $100\%$ 的数据，$1 \leq N \leq 2500$ ，$1 \leq T \leq 1000$ ，$1 \leq X_i \leq 1000$ 。

输出格式

输出一个整数，即把所有同学摆渡到河对岸的最少时间。

示例

• 示例1
  • 输入

5 8
2
4
3
50
2

输出

39

解释：小A老师独自过河需8分钟。先载3名同学过河，时间为 $8 + 2 + 4 + 3 = 17$ 分钟，再独自返回需8分钟，最后载剩下2名同学过河，时间为 $8 + 2 + 4 = 14$ 分钟，总用时 $17 + 8 + 14 = 39$ 分钟。 示例2

输入

6 12
4
8
1
9
3
1

• 输出

38

示例3 输入

10 20
1
2
1
2
1
2
1
2
1
2

输出

35