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(az) 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
surajxd:
20200904 06:05:28
@s_tank00_ jhut kahe bolta hai re 999 to tmhara total attempt v nhi hai.


s_tank00_:
20200826 08:46:40
didnt got accepted even after 999 go Last edit: 20200826 09:51:13 

shubham_it_bit:
20200825 09:53:22
Good one.. :) ... small extension of LCS 

arman____:
20200507 09:21:50
good problem..LCS+Knapsack..LCS+Sorting give WA.. 

pratiikgoogler:
20200310 08:48:05
My 3rd 3D DP problem :) 

aryan29:
20200124 20:07:14
DP ques after a while Last edit: 20200124 20:08:02 

gouravkandoria:
20191209 09:00:20
Alok Nath ji ko Pranaam! 

urimaj:
20190308 02:13:10
How can I solve it iteratively? 

sdeven_0245:
20180811 07:59:55
Easy problem 

akshitagarwal:
20180807 13:00:30
LCS and Reverse sorting the string obtained by backtracking what is the problem in this?? 
Added by:  Sanket Singhal 
Date:  20150218 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  Own Problem(CQM 8 BIT Mesra) 