favorite We need a little bit of your help to keep things running, click on this banner to learn more

2018 Цикл Интернет-олимпиад для школьников

Rats eating

Kratos and Atreus decided to eat fried rats. To diversify the process, Kratos prepared 2k rats and offered to arrange a speed-eating competition.

Both Kratos and Atreus will eat k fried rats. It all ended as fast as it started. Freya secretly watched this contest and noticed several features:

  • Both contestants ate exactly k rats.
  • In one action, Kratos or Atreus ate either one or two rats.
  • Each time one of them took an action, he recorded how many rats he ate.

After Kratos and Atreus left, Freya found their “protocol." Unfortunately, for each action, it is recorded how many rats were eaten, but it was not recorded who exactly ate them.

Freya remembers that at some point in the competition, Kratos looked like an unconditional leader, since he ate rats much more than Atreus. She asks you, according to this protocol, to determine what the largest gap Kratos could have during the competition.


First line contains two integers n and k (2n105, 1kn) - the number of entries in the protocol and the number of rats eaten by each of the participants.

Second line contains n integers ai (1ai2) - the protocol data. It is guaranteed that the protocol is correct: you can divide ai into two sets so that the sum of the numbers in both sets is k.


Print a single integer - the largest advantage of Kratos during the match.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 2
1 2 1
Output example #1
Source 2018 Cycle of Internet Olympiads for schoolchildren, second team season olympiad, Basic nomination, October 20, Problem А