LCS stands for longest common subsequence, and it is a well known problem. A sequence in this problem

means a list of integers, and a sequence X is considered a subsequence of another sequence Y, when the

sequence X can be obtained by deleting zero or more elements from the sequence Y without changing the

order of the remaining elements.

In this problem you are given two sequences and your task is to nd the length of the longest sequence

which is a subsequence of both the given sequences.

You are not given the sequences themselves. For each sequence you are given three integersN, FandD,

whereNis the length of the sequence, Fis the rst element in the sequence. Each element except the

rst element is greater than the element before it byD.

For exampleN= 5,F= 3 andD= 4 represents the following sequence: [3, 7, 11, 15, 19].

There will be at least one integer which belongs to both sequences and it is not greater than 1,000,000.