题目描述

Alex 喜欢玩网络游戏，认为这是智力和体力的综合锻炼。在一次游戏活动中，他意外获得了一个传说中威力极其强大的法宝：珠链。

珠链，顾名思义，就是由许多小珠子串起来的一条链。珠子有很多种颜色。Alex 听说过，只有将珠链打磨纯净，珠链才能发挥最大的威力。

纯净珠链是指这样的珠链：它可以分成若干个长度相等的段，使任何两段的任何相同位置的珠子的颜色均不同，相同位置指珠子在段内的相对位置相同；而且每段的长度以及划分的段数也是有规范的，Alex 记得，每段包含的珠子数目必须在 $L$ 到 $R$ 之间，而且划分的段数不能少于 $S$。

所谓打磨，就是从珠链的首和尾拿掉连续的若干个珠子。打磨后的纯净珠链的威力等于它的每个珠子具有的魔力值之和。

一个珠子的魔力值只与它在打磨前的珠链中的位置有关。在查找和分析了大量实验数据以后，Alex 发现珠子的魔力值等于珠子原来位置编号的约数个数！

兴奋不已的 Alex 想将珠链打磨成威力最大的纯净珠链。然而，马上要参加期末考试的 Alex 来不及计算了，你能否帮助 Alex 算出最大的威力值呢？

输入格式

第一行是四个整数 $N,L,R,S$。

第二行是一个长度等于 $N$ 的字符串，表示 Alex 得到的珠链。字符串的第 $i$ 个字符表示珠链的第 $i$ 个珠子的颜色。相同字母表示相同颜色。珠子的位置从 $1$ 编号到 $N$。

保证输入的字符串只包含大写和小写的英文字母，并且字母区分大小写。

输出格式

输出一行，表示打磨后的纯净珠链的最大威力值。

如果无法打磨成满足要求的纯净珠链，输出 -1。

7 2 3 2
abcbcaa

15

提示

【样例解释】

能够打磨出的合乎要求的纯净珠链有三种：$\texttt{bc/aa}$，$\texttt{abc/bca}$ 和 $\texttt{bcb/caa}$。其中威力最大的是第三种，其威力值等于 $2 + 2 + 3 + 2 + 4 + 2 = 15$。

如果给出的珠链是纯净珠链，那么可以不打磨。纯净珠链必须能划分成不少于 $S$ 个等长的段且每段长度在 $L$ 到 $R$ 之间。

【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 5 \cdot 10^5$，$1 \le L,R,S \le N$，$0 \le R - L \le 10$。