Training Site
Sideways banner

Construction

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 10 megabytes
Time limit: 10.0 seconds

Brenda the Builder specializes in building two-dimensional apartment blocks in mountainous areas. However, she is always looking for ways to cut costs.

Before starting to build, Brenda must first level the ground to create the foundation for her building. Brenda has access to a strip of land of length N with varying heights, modelled as a series of integer height blocks H_0, H_1, ..., H_{N-1}. She would like to level K contiguous blocks of land to create a foundation. The cost of building the foundation is equal to the height of the highest block to be levelled minus the height of the lowest block to be levelled.

Your job is to help Brenda by computing the lowest possible cost of building her foundation.

Input

The input consists of two lines.

The first line will contain two positive integers N and K, representing the number of land blocks and the length of the foundation. It is guaranteed that K \leq N.

The second line will contain N space-separated integers H_i, representing the height of the land for that block. It is guaranteed that 0 \leq H_i \leq 10^9.

Output

The output should be a single integer: the lowest possible cost for Brenda's foundation.

Note: Python submissions could take as much as 40 seconds to process so submitting too frequently will clog up our server.

Subtasks

  • Subtask 1 (45%): N \leq 1,000
  • Subtask 2 (40%): N \leq 100,000
  • Subtask 3 (15%): N \leq 300,000

For Subtask 3, you need to think of a faster algorithm you could use.

  • Sample Input 1

    3 2
    4 1 2
    

    Sample Output 1

    1