6. You receive two strings X and Y, over the alphabet ? = {ABC...Z}. In addition, for every letter l in the alphabet, you are given a weight (a value) w() for this letter. For example, W(A) = 3, w(B) = 1, w(C) = 17, w(D) = 1, ...W(Z) = 12 We define the weight of a string s to be the sum of weights of each letter in s. For example, w("ZABZ") = 12+ 3+1 + 12 = 26. Note that 2 appears twice is "ZABZ, hence its weight counted twice. Suggest a modification of the LCS algorithm, such that the new algorithm finds a subse- quence s which is a common subsequence of X and of Y, with maximum weight. 2 Example. If X = "BABCD" and Y = "CBABD" then the new algorithm should return "CD". This is because the weight w("CD") is w("CD") = W('C') + w('D') = 17 +1. Note that "BABF" is a longer common subsequence, but W("BABD') = 1+3+1+1 = 6. Analyse the running time of your algorithm