You are given three integers $$$x, y, z$$$ and a string $$$S$$$ consisting of $$$n$$$ lowercase English letters.
For four integers $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, $$$r_2$$$ where $$$(1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt n)$$$, let's define the function $$$F$$$ as follows:
You need to find four integers $$$l_1, r_1, l_2, r_2$$$ where $$$(1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt n)$$$ that maximize the value $$$F(l_1, r_1, l_2, r_2)$$$ and satisfy the following conditions:
Note that $$$S[l...r]$$$ is a substring of the string $$$S$$$ that starts from position $$$l$$$ and ends at position $$$r$$$, more formally $$$S[l...r] = S_{l} S_{l+1} ... S_{r-1} S_{r}$$$, and if $$$l \gt r$$$ then $$$S[l..r]$$$ is an empty string.
If there are no integers $$$l_1, r_1, l_2, r_2$$$ satisfying the mentioned conditions, print $$$0$$$.
The first line contains four integers $$$n,x,y,z$$$ $$$(4 \le n \le 10^6, 1 \le x,y,z \le 10^9)$$$ — where $$$n$$$ is the number of letters in the string $$$S$$$.
The second line contains the string $$$S$$$, consisting of $$$n$$$ lowercase English letters.
Output a single integer — the maximum possible value of the function $$$F$$$, and if there are no integers $$$l_1, r_1, l_2, r_2$$$ satisfying the mentioned conditions, print 0.
14 5 10 1abreabqqytpsyt
32
5 2 3 5aaaaa
10
In the first test, the four integers are $$$l_1 = 5, r_1 = 6, l_2 = 9, r_2 = 10$$$.
$$$S[5...6] = ab$$$ which equals to a prefix of $$$S$$$.
$$$S[9...10] = yt$$$ which equals to a suffix of $$$S$$$.
$$$(6-5)*5 + (10-9)*10 + (9-6)*1 + 10 + 5 - 1 = 32$$$.
