You are given a string S (consisting of lowercase English characters).

In one operation, you can remove the substring "pr" from the string S and get the amount X or you can remove the substring "rp" from the string S and get the amount Y.

Find the maximum amount you can get if you perform zero or more such operations optimally.

Note:
Substring of string S is defined as a continuous sequence of characters in S.
After removal of substring "pr" or "rp" from S, the rest of the characters in S remains in the same order.

Input Format:

1. First Line contains an integer T denoting the number of test cases.
2. First Line of each test case contains a string S.
3. Second Line of each test case contains two space-separated integers X and Y.

Output Format:

For each test case print a single integer denoting maximum amount you can get in a new line.

Constraints:

1 <= T <= 10
1 <= |S| <= 100000
1 <= X <= 100
1 <= Y <= 100

Sample Input:
3
abppprrr
5 4
prprprrp
7 10
abcdpqrpqr
3 4

Sample Output:
15
37
4

Explanation:

S = "abppprrr", X = 5, y = 4

Remove substrings as mentioned:

Remove "pr", new string S = "abpprr"
Remove "pr", new string S = "abpr"
Remove "pr", new string S = "ab"

In total, we remove "pr" 3 times. Hence answer is = 5+5+5 = 15

The idea behind the solution:

1. First, we check either X is greater than Y or not if X > Y then removing "pr" will give us greater value and if Y > X then "rp" gives more.
2. We should greedily remove "pr" or "rp" depending upon either X is greater or Y is greater.
3. We will be using a stack to keep the order same after removal of substrings.
4. After removing all possible "pr" we will check in rest of the string if any "rp" present and we will remove them and vice versa.

Python Solution

def rp(string, x, y, ans, flag):
    stack = []
    for char in string:
        if char == 'p':
            if stack and stack[-1] == 'r':
                ans[0] += y
                stack.pop()
            else:
                stack.append(char)
        else:
            stack.append(char)
    if flag:
        pr("".join(stack), x, y, ans, False)


def pr(string, x, y, ans, flag):
    stack = []
    for char in string:
        if char == 'r':
            if stack and stack[-1] == 'p':
                ans[0] += x  
                stack.pop()
            else:
                stack.append(char)
        else:
            stack.append(char)
    if flag:
        rp("".join(stack), x, y, ans, False)
    
def solve():

    string = input()
    x, y = map(int, input().split())
    ans = [0]

    if x  > y:
        pr(string, x, y, ans, True)
    else:
        rp(string, x, y, ans, True)
    print(ans[0])
        

for _ in range(int(input())):
    solve()

Complexity Analysis:

1. Time complexity is O(n), where n = length of string S.
2. Space Complexity O(n) extra auxilary space for the stack.