問題文

無限に広い二次元グリッドの原点 $(0, 0)$ に高橋君と $1$ 台のドローンがいます。このドローンは文字列が与えられた時、文字列の先頭から末尾までのそれぞれの文字を $1$ つの命令と解釈して順に実行します。命令は以下の $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、?の $5$ 種類の文字のみからなる。
• $2$ 行目に求める値の種類を表す整数 $T (1≦T≦2)$ が与えられる。

出力

• $T=1$ ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最大値を $1$ 行に出力せよ。
• $T=2$ ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最小値を $1$ 行に出力せよ。
• 改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $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

• このケースは部分点の追加制約を満たしません。

---