G - 回文スコア

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

文字列 S が与えられます。S に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。例えば S = aaab のとき、二つの回文 abaa を作ることができます。このように、文字は自由な順序で使用することができ、S に複数回現れる文字は合計でその回数だけ使用します。

長さ L の回文を 1 個作るごとに、L^2 のスコアが得られます。最大で合計いくつのスコアを得ることができるでしょうか?

制約

  • 1 ≦ |S| ≦ 100,000
  • S は小文字アルファベットのみからなる。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

得られる最大の合計スコアを出力せよ。


入力例 1

aaba

出力例 1

10

aaba からは二つの回文 abaa を作ることができます。このときに得られる合計スコアは 9+1=10 であり、これが得られる最大の値です。