该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的巡检航线

题目描述

徐老师使用一架无人机完成校园巡检。每次巡检开始时，无人机都位于无限二维网格的原点 $(0,0)$。

无人机会从左到右依次执行字符串中的每个字符。设执行某条指令前无人机位于 $(x,y)$，四种指令的含义如下：

• L：移动到 $(x-1,y)$；
• R：移动到 $(x+1,y)$；
• U：移动到 $(x,y+1)$；
• D：移动到 $(x,y-1)$。

一次巡检结束后，控制日志中保存了一段指令字符串 $S$，但其中一些字符已经损坏，变成了 ?。每个 ? 原本都是 L、R、U、D 中的一个字符，不同的 ? 可以表示不同的指令。

若无人机最终位于 $(x,y)$，它与原点的距离定义为曼哈顿距离 $|x|+|y|$。

为了评估日志缺失带来的影响，给定分析模式 $T$：

• 当 $T=1$ 时，求所有可能的原指令中，无人机最终距离的最大值；
• 当 $T=2$ 时，求所有可能的原指令中，无人机最终距离的最小值。

输入格式

第一行包含一个字符串 $S$（$1\le |S|\le 10^5$）。字符串只包含 L、R、U、D、? 这五种字符。

第二行包含一个整数 $T$（$1\le T\le 2$）。

输出格式

如果 $T=1$，输出无人机最终距离的最大可能值。

如果 $T=2$，输出无人机最终距离的最小可能值。

输入输出样例 #1

输入 #1

UL?
1

输出 #1

3

输入输出样例 #2

输入 #2

UD?
1

输出 #2

1

说明/提示

样例 #1

无人机最终可能位于 $(-2,1)$、$(-1,0)$、$(-1,2)$、$(0,1)$，其中最大的曼哈顿距离为 $3$。

样例 #2

无人机最终可能位于 $(1,0)$、$(-1,0)$、$(0,1)$、$(0,-1)$，这些位置与原点的距离都是 $1$。