AIOC Banner

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:

Additionally, for 50% of these marks:

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
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 26 August 2019,  4:12am AEST