# Problem: Memories

Want to try solving this problem? You can submit your code online if you log in or register.

## Memories

Time Limit: 2 seconds
Memory Limit: 16 Mb

It is the start of a new year at Petit's School for Proper and Well-Balanced Children, and as the Chief Record Keeper it is your job to take the school photograph. Your training in the art houses of Europe has taught you that form is more important than content--with this in mind, you decide that it does not matter who is in the photograph as long as it looks good.

You decide to form R rows of children, with C children in each row. For each row, the imbalance of the row is the difference between the height of the shortest student in that row and the height of the tallest student in that row. The imbalance of the entire photograph is the largest imbalance seen in any of the rows.

There are N students in the school, all of whom are eager to have their photo taken. To save your reputation as both an artist and a well-balanced teacher, your task is to choose R  x  C of these students for your photograph so that the imbalance of the photograph can be made as small as possible.

As an example, suppose there are N=8 students in the school, with the following heights (all measured in centimetres):

170, 205, 225, 190, 260, 130, 225, 160.

Suppose you need to form R=2 rows of C=3 students each. You can do this as follows:

 Row 1: Heights 225, 205, 225 Row 2: Heights 160, 190, 170

The imbalance of row 1 is 225-205 = 20, and the imbalance of row 2 is 190-160=30. Therefore the imbalance of the entire photograph is (20,30)=30, which in fact is the smallest imbalance possible.

### Constraints

For 100% of the available marks:

• 1  ≤ R  ≤ 10,000 and 1  ≤ C  ≤ 10,000, where R is the number of rows in your photograph and C is the number of students in each row.
• R  x  C  ≤ N  ≤ 1,000,000, where N is the total number of students in the school.
• 1  ≤ H  ≤ 1,000,000,000, where H is the height of a student as measured in centimetres. Something must be done about those high-energy school lunches.
Additionally, for 50% of these marks:
• N ≤ 5000.

### Input

Your program must read from standard input. The first line of input will contain the integers N R C, as described above. Following this will be N additional lines of input, each giving the height of a student (measured in centimetres).

### Output

Your program must write a single line to standard output. This line must contain a single integer, giving the smallest possible imbalance for your photograph (again in centimetres).

### Sample Input

8 2 3
170
205
225
190
260
130
225
160


### Sample Output

30


### Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

Privacy statement
Page generated: 24 March 2023,  8:12pm AEDT