Problem Statement

There are two buttons, one of size A and one of size B.

When you press a button of size X, you get X coins and the size of that button decreases by 1.

You will press a button twice. Here, you can press the same button twice, or press both buttons once.

At most how many coins can you get?

Constraints

• All values in input are integers.
• 3 \leq A, B \leq 20

Sample Input 1

5 3

Sample Output 1

9

You can get 5 + 4 = 9 coins by pressing the button of size 5 twice, and this is the maximum result.

Sample Input 2

3 4

Sample Output 2

7

Sample Input 3

6 6

Sample Output 3

12

Problem Statement

There are N mountains ranging from east to west, and an ocean to the west.

At the top of each mountain, there is an inn. You have decided to choose where to stay from these inns.

The height of the i-th mountain from the west is H_i.

You can certainly see the ocean from the inn at the top of the westmost mountain.

For the inn at the top of the i-th mountain from the west (i = 2, 3, ..., N), you can see the ocean if and only if H_1 \leq H_i, H_2 \leq H_i, ..., and H_{i-1} \leq H_i.

From how many of these N inns can you see the ocean?

Constraints

• All values in input are integers.
• 1 \leq N \leq 20
• 1 \leq H_i \leq 100

Sample Input 1

4
6 5 6 8

Sample Output 1

3

You can see the ocean from the first, third and fourth inns from the west.

Sample Input 2

5
4 5 3 5 4

Sample Output 2

3

Sample Input 3

5
9 5 6 8 4

Sample Output 3

1

Problem Statement

N tiles are arranged in a row from left to right. The initial color of each tile is represented by a string S of length N.

The i-th tile from the left is painted black if the i-th character of S is 0, and painted white if that character is 1.

You want to repaint some of the tiles black or white, so that any two adjacent tiles have different colors.

At least how many tiles need to be repainted to satisfy the condition?

Constraints

• 1 \leq |S| \leq 10^5
• S_i is 0 or 1.

Sample Input 1

000

Sample Output 1

1

The condition can be satisfied by repainting the middle tile white.

Sample Input 2

10010010

Sample Output 2

3

Sample Input 3

0

Sample Output 3

0

Problem Statement

N people are arranged in a row from left to right.

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.

You will give the following direction at most K times (possibly zero):

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most K directions.

Constraints

• N is an integer satisfying 1 \leq N \leq 10^5.
• K is an integer satisfying 1 \leq K \leq 10^5.
• The length of the string S is N.
• Each character of the string S is 0 or 1.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

• Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.