Background

农夫约翰要带着 N 头奶牛渡过一条河，唯一的渡河工具是一艘木筏。由于奶牛不会划船，整个渡河过程中，约翰必须始终在木筏上，否则木筏无法移动。 渡河时间会随木筏上的奶牛数量增加而变长： 约翰独自划木筏过河，需要 M 分钟； 每多带 1 头奶牛，渡河时间会额外增加一段固定时长：带 1 头奶牛时，额外增加 M₁ 分钟；带 2 头奶牛时，在带 1 头的基础上再额外增加 M₂ 分钟；以此类推，带 k 头奶牛时，总渡河时间为 M + M₁ + M₂ + ... + Mk 分钟。 约翰需要往返多次才能将所有奶牛带到对岸（最后一次渡河无需返回），返回时需独自划木筏（耗时 M 分钟）。请计算将所有 N 头奶牛全部带到对岸的最短总时间。

Format

Input

第一行包含两个整数 N 和 M，分别代表奶牛的总数和约翰独自渡河的时间（分钟）。 接下来 N 行，第 i+1 行包含一个整数 Mᵢ（1 ≤ i ≤ N），代表 “奶牛数量从 i-1 增加到 i 时” 额外增加的渡河时间（分钟）。

Output

输出一行一个整数，代表将所有奶牛全部渡过河的最短总时间（分钟）。

Samples

5 10 
3 
4 
6 
100 
1 

50 

Limitation

1s, 1024KiB for each test case.

样例解释 时间计算规则 独自渡河：10 分钟； 带 1 头奶牛：10 + 3 = 13 分钟； 带 2 头奶牛：10 + 3 + 4 = 17 分钟； 带 3 头奶牛：10 + 3 + 4 + 6 = 23 分钟； 带 4 头奶牛：10 + 3 + 4 + 6 + 100 = 123 分钟； 带 5 头奶牛：10 + 3 + 4 + 6 + 100 + 1 = 124 分钟。 最优渡河方案 带 3 头奶牛过河，耗时 23 分钟； 独自返回，耗时 10 分钟； 带剩余 2 头奶牛过河，耗时 17 分钟； 总时间：23 + 10 + 17 = 50 分钟。 数据规模与约定 1 ≤ N ≤ 2500（奶牛总数不超过 2500 头）； 1 ≤ M ≤ 1000（独自渡河时间不超过 1000 分钟）； 1 ≤ Mᵢ ≤ 1000（每增加 1 头奶牛的额外渡河时间不超过 1000 分钟）。