题目描述

经过精心的计算，卡卡西终于帮助白胡子和黑胡子两位巫师分出了胜负，他们也遵守承诺打开了锁链。最终，卡卡西在四又四分之三号站台登上“和谐号”魔法快车，来到了世界魔法大学的门口。但此时她却惊讶地发现魔法大学被石头紧紧裹住，转了一圈也没有发现大门，这是怎么回事呢？

原来，大学门口有一个很大的广场，而广场的顶部有着大小不一的长方形透光栅格，这些格子沿着屋顶的一侧整齐地排列着，它们的底部宽度一样，但是高度随着阳光照射的角度不同而时刻变化着，并在地上投影出变化着的影子，而这些影子所组成的直方图里面的最大矩形就是变化着的学校的大门——阴影之门。你能帮助卡卡西找出阴影之门的变化规律，准确说出阴影大门的面积，从而进入魔法学校么？

在横轴上放了$n$个相邻的矩形，每个矩形的宽度是$w$（所有矩形宽度一致），而第$i$（$1 \leq i \leq n$）个矩形的高度是$h_i$。这$n$个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是4, 2, 6, 5, 1, 7。宽度$w=2$。

说明：请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形为下图所示的红色部分，面积是20。

输入格式

输入数据共两行，第一行包含两个正整数$n$和$w$（空格隔开），分别表示矩形的数量和矩形的宽度。第二行包含$n$个整数$h_1, h_2, \dots, h_n$，相邻的数之间由空格分隔，$h_i$是第$i$个矩形的高度。

输出格式

一个正整数，表示给定直方图内的最大矩形的面积。

样例

输入#1

6 2
4 2 6 5 1 7

输出#1

20

数据范围

数据范围：
$1 \leq n \leq 1000$，$1 \leq h_i \leq 10000$，$1 \leq w \leq 100$