Maximizing the Power of the Purified Bead Chain

Alex, an avid online gamer, obtained a legendary magical bead chain. The chain consists of beads of various colors. Alex learned that to unlock the chain's full power, one must "polish" it by removing some beads consecutively from the beginning and/or the end so that the remaining (contiguous) subchain is pure.

A subchain is considered pure if there exists an integer l (the segment length) and an integer m (the number of segments) such that:

• The length of the subchain is M = m \times l.
• \( l \in [L, R] \).
• \( m \ge S \).
• When the subchain is divided into m consecutive segments (each of length l), for every position \( p = 1, 2, \dots, l \), the beads in the \( p^{th} \) position of each segment are pairwise different. (In other words, for any two segments, the beads at the same relative position must have different colors.)

The power of a purified bead chain is defined as the sum of the magic values of its beads. The magic value of a bead is determined solely by its original position in the chain (numbered from 1) and is equal to the number of positive divisors of that position. For example, the bead at position 6 has a magic value of 4 since 6 has divisors 1, 2, 3, and 6.

Your task is to help Alex by finding the maximum power value for any purified subchain that can be obtained by polishing the original bead chain (i.e. choosing an appropriate contiguous subchain). If no purified subchain exists, output 0.

Input Format: The first line contains four space‐separated integers: N, L, R, and S, where N is the total number of beads, L and R specify the allowed range for the segment length, and S is the minimum number of segments required. The second line contains a string of length N representing the colors of the beads (each character stands for a color).

Output Format: Output a single integer — the maximum power value among all purified subchains, or 0 if no purified subchain exists.

Note (in LaTeX): The conditions for a subchain of length \(M\) to be purified can be summarized as: \[ \begin{aligned} &\exists\ l, m \text{ such that } M = m \times l,\\ &l \in [L, R],\\ &m \ge S,\\ &\text{and for each } p = 1, 2, \dots, l, \text{ the beads at positions } p, p+l, \dots, p+(m-1)l \text{ are all distinct.} \end{aligned} \]

inputFormat

Input begins with a line containing four integers:
N L R S

• N: total number of beads.
• L, R: inclusive range for the segment length when splitting the subchain.
• S: minimum number of segments required.

The second line contains a string of N characters, where each character indicates the color of a bead.

Example:
8 2 3 2
ABACABCD

outputFormat

Output a single integer — the maximum power value of any purified subchain. If no such subchain exists, output 0.

Example:
11

sample

8 2 3 2
ABACABCD

11