Problem Description

There is an infinite 2D grid, and Takahashi and a drone are at the origin $ (0, 0) $. When given a string, the drone interprets each character from the beginning to the end of the string as a command and executes them in order. There are four types of commands:

• L moves the drone from position $ (x, y) $ to $ (x-1, y) $.
• R moves the drone from position $ (x, y) $ to $ (x+1, y) $.
• U moves the drone from position $ (x, y) $ to $ (x, y+1) $.
• D moves the drone from position $ (x, y) $ to $ (x, y-1) $.

The drone has received some commands and moved somewhere. Takahashi has obtained the string $ S $ representing the commands sent to the drone, but some parts of it have been damaged and turned into ?. It is known that each ? was originally one of the characters L, R, U, or D.

The distance between the drone and Takahashi is represented by the Manhattan distance $ |x|+|y| $, where $ (x, y) $ is the position of the drone. Given an integer $ T $ indicating the type of value to find, determine the possible distance between the drone and Takahashi after the movement: if $ T=1 $, find the maximum distance; if $ T=2 $, find the minimum distance.

Input Format

The input is given from the standard input in the following format:

$ S $ $ T $

• The first line contains the string $ S $ representing the commands given to the drone, where $1 \leq |S| \leq 10^5$. Here, $ |S| $ denotes the length of the string $ S $.
• $ S $ consists only of the characters L, R, U, D, and ?.
• The second line contains an integer $ T $ $(1 \leq T \leq 2)$ indicating the type of value to find.

Output Format

• If $ T=1 $, output the maximum possible distance between the drone and Takahashi after the movement on a single line.
• If $ T=2 $, output the minimum possible distance between the drone and Takahashi after the movement on a single line.
• Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

UL?
1

Sample Output #1

3

Sample Input #2

UD?
1

Sample Output #2

1

Sample Input #3

UUUU?DDR?LLLL
1

Sample Output #3

7

Sample Input #4

UULL?
2

Sample Output #4

3

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all datasets for $ T=1 $, you will be awarded 100 points.
• If you correctly solve all datasets without additional constraints, you will be awarded an additional 1 point, totaling 101 points.

Sample Explanation 1

• The possible final positions of the drone are $ (-2,1), (-1,0), (-1,2), (0,1) $. The maximum distance $ |x|+|y| $ is 3. - This case satisfies the additional constraints for partial points.

Sample Explanation 2

• The possible final positions of the drone are $ (1,0), (-1,0), (0,1), (0,-1) $. The maximum distance $ |x|+|y| $ is 1. - This case satisfies the additional constraints for partial points.

Sample Explanation 3

• This case satisfies the additional constraints for partial points.

Sample Explanation 4

• This case does not satisfy the additional constraints for partial points.

见题面 Input 部分

见题面 Output 部分