Eavesdropper Evasion

Alice wants to send $n$
messages to Bob over a communication channel. The $i$th message takes $t_ i$ time steps to send. At each
*integer* time step, Alice can start sending any number
of her messages. Once started, a message must be transmitted in
its entirety (it cannot be paused and resumed later). Any
number of messages can be sent in parallel over the channel
without affecting the transmission time of individual
messages.

An attacker has the capability to disable the security
protocols of the channel for an interval of $x$ continuous time steps, but only
once (i.e., after doing this, they cannot wait a while and then
disable it for another $x$
time steps). While the security is disabled, the attacker is
able to listen in, and any message that is sent *in its
entirety* during those $x$ time steps is considered
exposed.

What is the minimum time needed for Alice to send all
$n$ messages to Bob so
that *at most* two messages are exposed, no matter when
the attacker chooses to disable the security?

The first line of input contains the two integers $n$ and $x$ ($1 \leq n \leq 20\, 000$, $1 \leq x \leq 10\, 000$), the number of messages Alice wants to send and the number of time steps someone may listen in. This is followed by a line containing $n$ integers $t_1, \ldots , t_ n$ ($1 \leq t_ i \leq 10\, 000$), the number of time steps it takes to transmit each message.

Output the minimum number of time steps to complete transmission of all $n$ messages so that at most two of them can be exposed.

Sample Input 1 | Sample Output 1 |
---|---|

6 10 2 3 4 5 6 7 |
16 |

Sample Input 2 | Sample Output 2 |
---|---|

7 6 9 3 2 3 8 3 3 |
11 |