AC報酬: $3$ ラテコイン

Story

🌊

matcharate君は無限に広いプールで遊んでました。ここのプールの監視員であるwatchrate君は、今日もプールの安全を見守っています。
するとwatchrate君はプールで遊んでいる人たちにこう報告してきました。

「今からプールになんか数字が書かれたコインをたくさん落としまーす！なので、全員所定の位置に移動して、そこの位置から拾ったコインを最大まで集めた人が、賞金を差し上げます！！」

matcharate君はwatchrate君がどんな心広い人か、そして意味わからない人かを認識することができたようです。

問題

無限に広いプールに、matcharate君が座標 $(0,0)$ に立っています。
matcharate君は今から $N$ 回の移動を行いますが、それは U, R, L, D からなる長さ $N$ の文字列 $S$ で表されます。
そのうち $S$ の $i\ (1\le i\le N)$ 文字目 $S_i$ は $i$ 回目の移動を表し、$S_i$ の文字によって以下のようにプールを移動します。ただし $(x,y)$ は今いるmatcharate君の座標を表します。

• $S_i=$ U のとき: 座標 $(x,y)$ から $(x,y+1)$ に移動する
• $S_i=$ R のとき: 座標 $(x,y)$ から $(x+1,y)$ に移動する
• $S_i=$ L のとき: 座標 $(x,y)$ から $(x-1,y)$ に移動する
• $S_i=$ D のとき: 座標 $(x,y)$ から $(x,y-1)$ に移動する

また座標 $(x,y)$ には整数 $X_{x,y}=Ax^2+By+C$ が書かれたコインが置かれてあり、matcharate君は移動毎にそのコインを集めていきます。
ここで、既に訪れた座標にもう一度移動したとしてもコインを集めます。また $(0,0)$ にあるコインも集めることに注意してください。

-Mission-
このとき、各移動毎に集めたコインにおいて、そのコインに書かれた整数の和の最大値としてあり得る値はいくつか。報告せよ。
すなわち $0,1,2,...,k$ 回目の移動で集めたコインに書かれた整数 $c_0,c_1,...,c_k$ において $X_k=c_0+c_1+...+c_k$ とするとき、$\max(X_0,X_1,...,X_N)$ を求めよ。

入力

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

制約

• $1\le N\le 10^5$
• $|A|,|B|,|C|\le 100$
• $S$ は U, R, L, D からなる長さ $N$ の文字列
• $N,A,B,C$ は整数

出力

答えを出力せよ。

入出力例

3
1 2 3
URL

19

$(0,0),(0,1),(1,1),(0,1)$ の順に移動します。$(0,0),(0,1),(1,1)$ には以下のような整数が書かれたコインを集めます。

• $(0,0)$ : $X_{0,0}=1\times 0^2+2\times 0+3=3$
• $(0,1)$ : $X_{0,1}=1\times 0^2+2\times 1+3=2+3=5$
• $(1,1)$ : $X_{1,1}=1\times 1^2+2\times 1+3=1+2+3=6$

よって集めたコインに書かれた整数はそれぞれ $3,5,6,5$ となり、その和は $19$ です。この $3$ 回の移動において $19$ 以上になることはありません。

1
1 4 3
D

3

$(0,0),(0,-1),(0,0)$ の順に移動します。$(0,0),(0,-1)$ には以下のような整数が書かれています。

• $(0,0)$ : $X_{0,0}=1\times 0^2+4\times 0+3=3$
• $(0,-1)$ : $X_{0,1}=1\times 0^2+4\times (-1)+3=(-4)+3=-1$

ここで移動前に集めたコインに書かれている整数 $\{3\}$ の和は $3$ ですが、$1$ 回目の移動後で $\{3,-1\}$ となり、和は $2$ となります。
移動前に集めたコインに書かれた整数の和が最大値となるので、$3$ を出力します。

4
0 0 0
URLD

0

どれだけ移動しても最大値が変動しないこともあります。

15
3 -5 4
URURULDRURDLULL

49