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 blessing is in the form of a string consisting of lowercase characters (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

First line consists of the 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

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

Constraints

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

Sample

Input:
2
asdf
asdf
3
anandi
jagya
3

Output:
317
0

hide comments
vl4deee11: 2024-03-21 17:30:17

use only trenary, its fun!

Last edit: 2024-03-21 17:30:44
lichaotree22: 2023-09-15 02:53:09

take it easy

imkabir_2001: 2022-01-12 08:52:37

@arman____ yes lcs + taking all choosing all string of length>=K and sorting gives WA. but y

surajxd: 2020-09-04 06:05:28

@s_tank00_ jhut kahe bolta hai re 999 to tmhara total attempt v nhi hai.

s_tank00_: 2020-08-26 08:46:40

didnt got accepted even after 999 go

Last edit: 2020-08-26 09:51:13
shubham_it_bit: 2020-08-25 09:53:22

Good one.. :) ... small extension of LCS

arman____: 2020-05-07 09:21:50

good problem..LCS+Knapsack..LCS+Sorting give WA..

pratiikgoogler: 2020-03-10 08:48:05

My 3rd 3D DP problem :)

aryan29: 2020-01-24 20:07:14

DP ques after a while

Last edit: 2020-01-24 20:08:02
gouravkandoria: 2019-12-09 09:00:20

Alok Nath ji ko Pranaam!


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