9062. Buns eating

 

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

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

·        Both contestants ate exactly k buns.

·        In one action, Kratos or Atreus ate either one or two buns.

·        Each time one of them took an action, he recorded how many buns he ate.

 

After Kratos and Atreus left, Freya found their “protocol”. Unfortunately, for each action, it is recorded how many buns 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 buns much more than Atreus. She asks you, according to this protocol, to determine what the largest gap Kratos could have during the competition.

 

Input. The 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 buns eaten by each of the participants.

The 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.

 

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

 

Sample input

Sample output

3 2

1 2 1

1

 

 

SOLUTION

mathematics

 

Algorithm analysis

The answer is k unless Kratos ate all his k buns first, and then Atreus ate all his buns. If there is a partial sum equal to k, then this case occurs, and the answer is k.

Otherwise, you can always organize eating buns in such a way that the answer is k – 1. In this case, there is a partial sum equal to k – 1, and Kratos must eat all the initial k – 1 buns. It is at this moment that Kratos’ lead will be k – 1. Next, according to the protocol, the number 2 follows, Atreus eats two buns. And in the future, the gap between Kratos and Atreus can no longer be greater than k – 2.

 

Algorithm realization

Read the input data.

 

scanf("%d %d", &n, &k);

 

Compute the partial sums in the variable s.

 

s = 0;

for (i = 0; i < n; i++)

{

  scanf("%d", &val);

  s += val;

 

If the partial sum at some moment is equal to k, then the answer to the problem is k.

 

  if (s == k)

  {

    printf("%d\n", k);

    return 0;

  }

}

 

Otherwise, print the answer k – 1, that can always be achieved.

 

printf("%d\n", k - 1);