小 P 和小 B 喜欢玩游戏,他们找到了 skip。skip 告诉了他们这样一个游戏:
- 有一个包含小写字母的字符串
,游戏开始时其为 skip 给定的一个字符串 。游戏对小 P 和小 B 计算分数,初始他们的分数都为 。 - 小 P 和小 B 轮流在这个串上操作,小 P 先手。每次操作方可以进行以下操作:
- 选择
的一个非空前缀(可以是 本身),获得等同于这个前缀在 中的出现次数的分数,并将这个前缀从 中删掉。
- 选择
- 如果进行了某次操作后
变为空,游戏就结束了。
为了让你更好的理解游戏规则,考虑如下例子:
- 初始时,
; - 小 P 选择
的前缀 ,获得 3 分, 变为 ; - 小 B 选择
的前缀 ,获得 2 分, 变为 ; - 小 P 选择
,获得 1 分,字符串变为空,游戏结束。最终小 P 获得 4 分,小 B 获得 2 分。
小 P 希望最大化小 P 的得分减去小 B 的得分,而小 B 希望最小化这个值。他们想知道在双方都绝顶聪明的情况下,最终小 P 的得分减去小 B 的得分会是多少。
输入格式
标准输入读入数据。
输入仅一行一个小写字母构成的字符串
输出格式
输出到标准输出。
一个整数,表示双方绝顶聪明的前提下,游戏结束时小 P 的得分减去小 B 的得分的值。
样例 #1
样例输入 #1
ababa
样例输出 #1
2
提示
样例 1 解释
小 P 和小 B 的最优策略为题目描述中给出的策略。
子任务
设
子任务编号 | 特殊性质 | 分值 | |
---|---|---|---|
1 | 无 | 10 | |
2 | 10 | ||
3 | 5 | ||
4 | 25 | ||
5 | 无 | 25 | |
6 | 无 | 25 |
时间限制:2s
空间限制:512MB