经过一场艰苦的战斗，李将军取得了伟大的胜利。现在，国家元首决定以荣誉和财富来奖励他所做的伟大贡献。
其中一件宝物是一条由26种不同宝石组成的项链，项链的长度为n的链状结构（也就是说：n种宝石串在一起构成了这条项链，每种宝石只属于26种宝石中的一种。项链是链而不是环）
根据古典观点，项链是有价值的，如果而且只有当它是回文（项链在正反方向上看起来都一样）。然而，我们上面提到的项链可能不是一开始的回文。所以国家元首决定把项链切成两半，然后把它们都交给李将军。
同一种类的宝石都有相同的价值（可能是正的，也可能是负的，因为它们的质量-有些种类很漂亮，而有些则看起来像普通的宝石）。回文项链的价值等于宝石的价值之和。而不是回文的项链的值为零。
现在的问题是：如何切割给定的项链，使两个项链的价值之和最大。输出这个值。
有多组输入数据，
接下来一行，一个由小写字母构成的长度不超过500000的字符串，表示项链，26个字母代表26种宝石，'a'的价值是v1'b'的价值是v2...'z'的价值是v26