题目描述

给定一个仅含小写字母的字符串 $s$。你需要从中选出若干个字符构成一个子序列（保持原顺序），使得选取的字符价值之和最大。

每个字符的价值为其在字母表中的位置（$a$ 到 $z$ 分别对应 $1$ 到 $26$）。

限制条件：选出的子序列中，任意两个相邻选取的字符在原字符串中的位置之差至少为 $2$。换句话说，如果你选取了原字符串第 $p_i$ 个位置的字符（$i \gt 1$），则必须满足 $p_i - p_{i-1} \ge 2$。

输入格式

输入一行包含一个字符串 $s$。

输出格式

输出一行一个整数，表示满足条件的子序列的最大价值之和。

样例

azaazaz

78

提示

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$|s| \leq 10$；
• 对于 $40\%$ 的评测用例，$|s| \leq 300$；
• 对于 $70\%$ 的评测用例，$|s| \leq 5000$；
• 对于所有评测用例，$1 \leq |s| \leq 10^6$，字符串中仅包含小写字母。