SELECTION  Bucket Selection
After a long period working in his magical garden, Bratan Mahammad could grow flowers of N distinct kinds there. Since Tukezban's (Mahammad's love) birthday is coming, as a perfect gift, Mahammad wants to give her K bunches of flowers. Interestingly, each flower has a beautifulness x_{i} and the number of flowers of every kind is M. When preparing flower buckets, he has to be very careful: every bucket must consist of N flowers and surely, all flowers have to be distinct kind in each bucket. The overall beauty value of K buckets depends on the absolute difference between the beautifulness of the most beautiful flower of K buckets (max(x_{i})) and the least beautiful one (min(x_{i})). Help Mahammad minimize this difference.
Input
The first line of the input contains 3 positive integers, N, M and K, denoting the number of flower types, the number of flowers in each type, and the number of buckets needed, respectively. Then, the following N lines have 4 integers each, x_{i,1,} a_{i,} b_{i,}_{ }c_{i}.
Here x_{i,1} indicates the beautifulness of the first flower in ith type. And for remaining M  1 flowers, beautifulness value is calculated as x_{i, j} = (a_{i }* x_{i, j}_{1} + b_{i}) % c_{i} .
You can safely assume that N, M, K ≤ 2500 and K ≤ M. All numbers in input section fit 32bit signed nonnegative integers.
Output
Print the minimum possible difference in Kbuckets.
Example
Input:
2 3 2 2 2 3 9 2 1 2 10
Output:
4
Note:
The generated beauty values will be:
For i = 1: (2, 7, 8)
For i = 2: (2, 4, 6)
One optimal way is to choose buckets as (7, 4) and (8, 6) together, so the difference is 8  4 = 4
By the way, we should not choose (2, 4) and (7, 2), since 7  2 = 5, which is greater than 4.
hide comments
DOT:
20181130 21:40:50
@mahmud2690, thanks for the response. I changed my approach and got AC. Brilliant question. :) 

DOT:
20180819 12:13:38
Hello @mahmud2690, my solution is https://www.ideone.com/tsc2Qk. I keep getting TLE on the 10th test case. Can you please take a look at my code and suggest any tips on reducing the time? Thanks in advance.


sampatghosh:
20180320 07:01:39
what is the range of a,b,c?? Getting WA in 10th test case!!!! Last edit: 20180320 14:22:45 

hello_world123:
20180317 15:49:29
getting WA on 9th test case


mahmud2690:
20180315 19:14:15
re Vipul: yes, the most beautiful flower of all K buckets. 

Vipul Srivastava:
20180315 18:59:21
is the beauty value the difference between the most beautiful flower of all the K buckets and the least beautiful flower of all the K buckets? Last edit: 20180315 19:15:37 
Added by:  mahmud2690 
Date:  20180313 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Me, MYSELF & I 