2018 Цикл Интернет-олимпиад для школьников
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 (2 ≤ n ≤
105, 1 ≤ k ≤ n) - the number of entries in the protocol and the number of rats eaten by each of the participants.
Second line contains n integers
ai (1 ≤
ai ≤ 2) - 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.
3 2 1 2 1