问题

在一个无限广阔的二维网格上，高橋君和一架无人机位于原点$(0, 0)$。当给定一个字符串时，无人机将依次执行从字符串开头到末尾的每个字符作为一个命令执行。命令有以下4种类型：

• L：将当前无人机的位置$(x, y)$移动到$(x-1, y)$
• R：将当前无人机的位置$(x, y)$移动到$(x+1, y)$
• U：将当前无人机的位置$(x, y)$移动到$(x, y+1)$
• D：将当前无人机的位置$(x, y)$移动到$(x, y-1)$

现在，给定了一些命令让无人机移动了某个位置。虽然高橋君得到了表示命令的字符串$S$，但其中的一些字符损坏变成了?，不知道原来是什么字符。但是已知?原先是L、R、U、D中的某个字符。

无人机与高橋君之间的距离用无人机的位置$(x, y)$的曼哈顿距离$|x|+|y|$表示。给定整数$T$表示需要求的值的类型，请计算出无人机和高橋君在移动完成后可能的距离中，如果$T=1$，输出最大值；如果$T=2$，输出最小值。

---

输入

输入通过标准输入给出，具体格式如下：

$S$

$T$

• 第1行：给定的表示命令的字符串$S(1≦|S|≦10^5)$。其中，$|S|$表示字符串$S$的长度。
• $S$由L、R、U、D、?五个字符组成。
• 第2行：整数$T(1≦T≦2)$，表示需要求的值的类型。

输出

• 如果$T=1$，输出移动完成后无人机和高橋君之间可能的距离中的最大值。
• 如果$T=2$，输出移动完成后无人机和高橋君之间可能的距离中的最小值。
• 输出时不要忘记换行符。

部分点

本问题设有部分点。

• 对于$T=1$的数据集，如果全部正确，可得100分。
• 对于附加约束条件的数据集若全部正确，可额外获得1分，总共可得101分。

---

输入示例 1

UL?
1

输出示例 1

3

• 可能存在无人机最终所在的位置有$(-2,1), (-1,0), (-1,2), (0,1)$这4个位置。无人机和高橋君之间的距离$|x|+|y|$中的最大值是3。
• 此示例符合附加约束条件的要求。

---

输入示例 2

UD?
1

输出示例 2

1

• 可能存在无人机最终所在的位置有$(1,0), (-1,0), (0,1), (0,-1)$这4个位置。无人机和高橋君之间的距离$|x|+|y|$中的最大值是1。
• 此示例符合附加约束条件的要求。

---

输入示例 3

UUUU?DDR?LLLL
1

输出示例 3

7

• 此示例符合附加约束条件的要求。

---

输入示例 4

UULL?
2

输出示例 4

3

• 此示例不符合附加约束条件的要求。