Problem Statement

無限に広い二次元グリッドの原点 $(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$ ならば最小値を求めてください。

Input

入力は以下の形式で標準入力から与えられる。

S
T

• $1$ 行目にドローンに与えられた命令を表す文字列 $S(1≦|S|≦10^5)$ が与えられる。ここで、 $|S|$ は文字列 $S$ の長さを表す。
• $S$ はL、R、U、D、?の $5$ 種類の文字のみからなる。
• $2$ 行目に求める値の種類を表す整数 $T (1≦T≦2)$ が与えられる。

Output

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

部分点

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

• $T=1$ のデータセットに全て正解した場合 $100$ 点が与えられる。
• 追加制約のないデータセットに正解した場合、追加で $1$ 点が与えられ、合計 $101$ 点が得られる。