BVAAN - Balika Vadhu and Alok Nath


Anandi and Jagya were getting married again when they have achieved proper age. Dadi Sa invited Alok Nath to do the kanyadaan and give blessings. Alok Nath has 2 blessings. Each bessing is in the form of a string consisting of lowercase charaters(a-z) only. But he can give only one blessing of K length because some priest told him to do so. Thus he decides to generate a blessing using the other two blessings. While doing this he wants to ensure that happiness brought into their life by his blessing is maximum.


The generated blessing is a common subsequence of length K of the two blessings he has. Happiness of the blessing he generates is calculated by the sum of ASCII values of characters in the blessing and he wants the happiness to be maximum. If he is not able to generate a common subsequence of length K then the happiness is 0 (zero). Alok Nath comes to you and asks you to find the maximum happiness that can be generated by the two blessings he has. 


Input Specification
First line consists of number of test cases t. Each test case consists of two strings b1 (blessing 1),b2 (blessing 2) and an integer K, each of them in separate lines.


Output Specification
Output consists of t lines each containing an integer denoting the maximum happiness value that can be generated by the two blessings.


Constraint
1 <= t <= 50
1 <= length(b1) , length(b2) <= 100 
1 <= K <= 100


Sample Input
2
asdf
asdf
3
anandi
jagya
3

Sample Output
317
0

hide comments
kira28: 2016-12-27 14:27:07

Very good ques!!!
combination of two typical DP problems
#1 on the ranks yayy xD xD

Last edit: 2016-12-27 14:29:21
siddharth_0196: 2016-10-16 19:31:28

Any corner cases?
LCS+Knapsack is giving WA! :/

Riddhi: 2016-06-11 15:35:53

i\p
1
aaaaaazzzz
zzzzaaaaaa
4
o/p = 488

SUBHAM SANGHAI: 2016-05-24 09:33:35

@silverscar Try this test case :

2

abdc

dcab

2

dcab

abdc

2

Output:
199
199
This test case might help u,to figure out ur mistake

Last edit: 2016-05-24 09:34:42
karthik1997: 2016-01-06 13:21:03

If the lcs is less than k , ouput is 0
or else it is the sum of largest k ascii values right ????

vagisha: 2016-01-02 14:23:16

Nice combination of LCS and Knapsack :)

anshal dwivedi: 2016-01-02 09:18:50

yo papi!!! 200th of mine :) XD

alpha coder: 2015-12-08 18:13:23

gives the feel of recursion ! ;)

silverscar: 2015-12-07 08:57:56

Instead of doing it in O(nmk) I tried it by doing standard lcs, backtrack to get back the lcs string, reverse sort the string and add the values of the first k characters in the string. Please tell me what's wrong with my logic...!!

dkumarsingh: 2015-12-03 20:53:15

i'm getting wrong answer for my submission id 15772416 can u please tell me for which test cases my answer is wrong


Added by:Sanket Singhal
Date:2015-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: JS2
Resource:Own Problem(CQM -8 BIT Mesra)