Description

Alex likes playing online games and believes this is a combined training of intelligence and physical ability. In one game event, he accidentally obtained a legendary and extremely powerful artifact: a bead chain.

A bead chain, as the name suggests, is a chain made by stringing many small beads together. Beads can have many colors. Alex heard that only by polishing the bead chain to be pure can it unleash its maximum power.

A pure bead chain is defined as follows: it can be divided into several segments of equal length, such that for any two segments, the colors of beads at every same position are all different. “Same position” means the same relative position within a segment. Also, the segment length and the number of segments must satisfy certain rules: Alex remembers that the number of beads in each segment must be between $L$ and $R$, and the number of segments must be at least $S$.

Polishing means removing a consecutive number of beads from the beginning and from the end of the bead chain. The power of the polished pure bead chain equals the sum of the magic values of all its beads.

The magic value of a bead depends only on its position in the original bead chain before polishing. After looking up and analyzing a lot of experimental data, Alex found that the magic value of a bead equals the number of divisors of its original position index.

Excited, Alex wants to polish the bead chain into a pure bead chain with the maximum possible power. However, Alex is about to take the final exam and has no time to calculate. Can you help Alex compute the maximum power value?

Input Format

The first line contains four integers $N, L, R, S$.

The second line contains a string of length $N$, representing the bead chain Alex obtained. The $i$-th character of the string represents the color of the $i$-th bead. The same letter means the same color. Bead positions are numbered from $1$ to $N$.

It is guaranteed that the input string contains only uppercase and lowercase English letters, and letters are case-sensitive.

Output Format

Output one line, the maximum power value of the pure bead chain after polishing.

If it is impossible to polish it into a pure bead chain that meets the requirements, output -1.

7 2 3 2
abcbcaa

15

Hint

Sample Explanation

There are three pure bead chains that can be obtained by polishing: $\texttt{bc/aa}$, $\texttt{abc/bca}$, and $\texttt{bcb/caa}$. The third one has the greatest power, and its power value is $2 + 2 + 3 + 2 + 4 + 2 = 15$.

If the given bead chain is already a pure bead chain, then you do not need to polish it. A pure bead chain must be divisible into at least $S$ equal-length segments, and each segment length must be between $L$ and $R$.

Constraints

For $100\%$ of the testdata, $1 \le N \le 5 \cdot 10^5$, $1 \le L, R, S \le N$, and $0 \le R - L \le 10$.

Translated by ChatGPT 5