Bob hasn't been doing well in school lately, so his parents have decided to create an incentive to motivate him. Bob will be given some money depending on his results on the next ~N~ tests. The tests are ordered and labelled from ~1~ to ~N~ and the ~j^\text{th}~ test has already been assigned a value ~v_j~ by Bob's parents where ~v~ is a non-decreasing sequence. They have promised that for each test ~j~, they will award him with ~v_j~ times the number of his marks among the earlier ~j-1~ marks which he exceeded. In other words, if Bob's marks on the ~N~ tests are ~m_1, m_2, \dots, m_N~, then Bob will earn

$$\displaystyle \sum_{\substack{i<j\\ m_i<m_j}} v_j$$

Bob knows that his mark on a given test is directly proportional to the amount of effort he puts into that test and that this amount of effort is always a non-negative integer. He also knows that he has a limited total amount of effort ~E~. Can you help Bob determine how much money he can make?

Constraints

~1 \le v_i \le 1\,000~ for all ~1 \le i \le N~
~v_1 \le v_2 \le \dots \le v_N~

Subtask 1 [20%]

~1 \le N \le 50~
~0 \le E \le 1\,000~

Subtask 2 [30%]

~1 \le N \le 200~
~0 \le E \le 5\,000~

Subtask 3 [50%]

~1 \le N \le 1\,000~
~0 \le E \le 20\,000~

Input Specification

The first line contains two space-separated integers, ~N~ and ~E~.
The next line contains ~N~ space-separated integers, ~v_1, v_2, \dots, v_N~.

Output Specification

Output a single integer, the maximum amount of money Bob can earn.

Sample Input 1

3 2
1 2 3

Sample Output 1

6

Explanation for Sample 1

Bob should put ~0~ effort into the first two tests and ~2~ effort into the last test. That way, he earns ~0\cdot v_1 + 0\cdot v_2 + 2\cdot v_3 = 6~.

Sample Input 2

5 0
100 100 100 100 100

Sample Output 2

0