AlanL received candy grams from his friend [REDACTED]! He has ~N~ individual candies, which he organized in order to eat 1 for the next ~N~ days such that each day has a specific associated candy. Each candy has a sweetness value of ~a_i~, and because [REDACTED] is sweet AlanL wishes to maximize the sweetness he eats over the ~N~ days. However, if AlanL eats a 2 candies in a row with a sum greater than ~K~, he will spontaneously combust. Thus, sometimes AlanL must skip eating candies on certain days in order to live. Please help AlanL!

Input Specification

The first line will contain ~N, K\ (1 \le N \le 2 \times 10^5),\ (1 \le K \le 10^9)~.

The next line will contain ~N~ integers ~a_i\ (1 \le a_i \le 10^9)~.

Output Specification

The maximum sweetness that AlanL can eat from the candies.

Subtasks

Subtask 1 [30%]

~N \le 2000~

Subtask 2 [70%]

No further constraints.

Sample Input

5 5
5 1 2 3 4

Sample Output

6

Sample Explanation

Alan eats the second, third, and fourth candies.