Ami needs to overcome ~n ~ monsters. The ~ i ~-th monster will deplete Ami's power by ~ a_i~. Since the battles occur consecutively, Ami doesn't have time to recover. Ami will collapse if his remaining power is less than or equal to ~0~ after any battle.

For example: if Ami initially has ~10~ power, and the first monster's strength is ~ a_1 = 4~ , Ami will successfully pass the first battle and have ~6~ power left. If the second monster's strength is at least ~6~, Ami will be defeated in this battle.

Ami has carefully studied his opponents and knows their strengths are ~ a_1, a_2, ..., a_n~ . Additionally, Ami will bring armor that can block ~ k~ damage. In other words, if Ami uses this armor when fighting the ~ i ~-th monster, he will lose ~ max(0, a_i - k) ~ power. However, this armor can only be used for one battle, and Ami must use it optimally.

Ami wants to pass all ~ n ~ battles. How much initial power does he need to prepare at a minimum, knowing that Ami will use the armor optimally?

Input

• The first line contains two positive integers ~n~ and ~k~ (~n \leq 10^5~ and ~ k \leq 10^9~), representing the number of monsters and the power of the armor respectively.
• The second line contains ~n~ positive integers ~ a_1, a_2, ..., a_n ~ (~ 1 \leq a_i \leq 10^9 ~) representing the strengths of the ~n~ monsters.

Output

• Output a single integer which is the minimum initial power Ami needs to prepare before the battles.

Sample Input

5 5
1 2 6 7 3

Sample Output

15