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 xi 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(xi)) and the least beautiful one (min(xi)). 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, xi,1, ai, bi, ci.

Here xi,1 indicates the beautifulness of the first flower in i-th type. And for remaining M - 1 flowers, beautifulness value is calculated as xi, j = (ai * xi, j-1 + bi) % ci .

You can safely assume that  N, M, K ≤ 2500 and K ≤ M. All numbers in input section fit 32-bit signed nonnegative integers.

Output

Print the minimum possible difference in K-buckets

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: 2018-11-30 21:40:50

@mahmud2690, thanks for the response. I changed my approach and got AC. Brilliant question. :)

DOT: 2018-08-19 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.

re: your solution gets TLE/WA even in the 1st test case. Try to analyze the complexity of your code.

Last edit: 2018-08-20 16:19:25
sampatghosh: 2018-03-20 07:01:39

what is the range of a,b,c?? Getting WA in 10th test case!!!!

Last edit: 2018-03-20 14:22:45
hello_world123: 2018-03-17 15:49:29

getting WA on 9th test case
Any hints?

mahmud2690: 2018-03-15 19:14:15

re Vipul: yes, the most beautiful flower of all K buckets.

Vipul Srivastava: 2018-03-15 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: 2018-03-15 19:15:37

Added by:mahmud2690
Date:2018-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Me, MYSELF & I