Chef and LCS

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently, Chef learned how to solve the Longest common subsequence problem. Being a fan of Ekta Kapoor^{1}, he really likes problems which require finding something k^{th}. Please help him solve one such problem he encountered.
Chef wants to know the lexicographically k^{th} longest common subsequence of any two given strings A and B. In other words, let L be the length of LCS(A, B), S be the sorted set of all common sequences of A and B with length L, you should find S_{k}. Keep in mind that all elements of a set are distinct.
Input
The first line of input contains two integers n and k. The second line contains the string A, and the third contains the string B. Lengths of both A and B equal n.Output
Output lexicographically k^{th} longest common subsequence. If such a sequence doesn't exist, output 1.Constraints
 1 ≤ n ≤ 1000
 1 ≤ k ≤ 10^{9}
 Each character of A and B is a lowercase Latin letter.
Example
Input: 3 3 abc cba Output: c Input: 5 5 abcba bacab Output: 1 Input: 2 2 aa ab Output: 1
Explanation:
Example case 1. L = LCS(A, B) = 1. There are three common sequences with length L, S = {"a", "b", "c"}. Answer is "c".
Example case 2. L = LCS(A, B) = 3. There are four common sequences with length L, S = {"aca", "acb", "bca", "bcb"}. Answer is "1".
Example case 3. L = LCS(A, B) = 1. There is only one distinct common sequence with length L, S = {"a"}. Answer is "1".
Note: ^{1}Chef is not really a fan of Ekta Kapoor.Author:  mgch 
Editorial  http://discuss.codechef.com/problems/CHEFKLCS 
Tags  cook65, dynamicprogramming, lcs, medium, mgch 
Date Added:  9122015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions