题目描述

小 W 有一个用大写字母串成的项链，有一天，他想把项链从中间某位置剪断，拉成一条直线后形成一个线性的字母串，其价值为每个字母的字典序位置 $\times$ 位置号的和。

所谓字典序位置指该字母在 $26$ 个字母表中排在第几个位置；位置号指该字母在字符串中排在第几个位置。

现在的问题是：该从哪里截断，才能让这个线性串的价值最大？

如：WJOI 组成的项链， ，可能的截断后的线性串有：

IW 中间截断，拉直后是 WJOI，价值为： $23 \times 1+10 \times 2+15 \times 3+9 \times 4=124$ 。

JO 中间截断，拉直后是 OIWJ，价值为： $15 \times 1+9 \times 2+23 \times 3+10 \times 4=142$ 。

WJ 中间截断，拉直后是 JOIW，价值为： $10 \times 1+15 \times 2+9 \times 3+23 \times 4=159$ 。

OI 中间截断，拉直后是 IWJO，价值为： $9 \times 1+23 \times 2+10 \times 3+15 \times 4=145$ 。

其中最大的价值为： $159$ 。

输入

一个只包含大写英文字母的字符串，最大长度不超过 $100000$ 。

输出

一个整数，表示最大的价值。

样例

WJOI

159

说明

【数据范围】

$10\%$ 的数据，串长 $=1$ 。

另外 $10\%$ 的数据，串长 $=2$ 。

$50\%$ 的数据，串长 $≤1000$ 。

$100\%$ 的数据： $1≤$串长 $≤100000$ 。

来源

2019 年武进区第 12 届程序设计比赛试题-小学组 T5