#C7762. Flower Pot Placement Optimizer

    ID: 51669 Type: Default 1000ms 256MiB

Flower Pot Placement Optimizer

Flower Pot Placement Optimizer

You are given a row of houses located at distinct integer positions along a street. The positions are provided in non-decreasing order. Additionally, you are given an integer k representing the number of flower pots available.

Your task is to determine the maximum number of flower pots that can be placed following the placement rules described below:

  • A flower pot must be placed at an integer coordinate.
  • No flower pot is placed at a location that is already occupied by a house.
  • You cannot place more than k flower pots.
  • Under the rules provided, it turns out that if you have at least one flower pot, you are able to place exactly k pots.

Note: Even though the positions of the houses are given, the optimal strategy always allows placing exactly k pots (or 0 if k is 0). Your program should compute and output this number.

The following examples illustrate the requirement:

  • For houses at positions [1, 2, 3, 7, 10] with k = 3, the answer is 3.
  • For houses at positions [1, 2, 3, 7] with k = 2, the answer is 2.
  • For houses at positions [1, 2, 3] with k = 1, the answer is 1.

inputFormat

The input is given via stdin and consists of two lines:

  1. The first line contains two integers n and k, where n is the number of houses and k is the number of available flower pots.
  2. The second line contains n space-separated integers representing the positions of the houses in non-decreasing order.

outputFormat

Output a single integer via stdout — the maximum number of flower pots that can be placed according to the rules.

## sample
5 3
1 2 3 7 10
3