AT_abc116_d [ABC116D] Various Sushi

[problemUrl]: https://atcoder.jp/contests/abc116/tasks/abc116_d $ N $ 個の寿司があり、それぞれの寿司には「ネタ」$ t_i $ と「おいしさ」$ d_i $ のパラメータが設定されています。 あなたはこの $ N $ 個の寿司の中から $ K $ 個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。 - 「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。 - 「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。 - 「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を $ x $ としたとき、$ x*x $ である。 あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ t_1 $ $ d_1 $ $ t_2 $ $ d_2 $ $ . $ $ . $ $ . $ $ t_N $ $ d_N $

あなたの得られる「満足ポイント」の最大値を出力してください。

### 制約 - $ 1\ \leqq\ K\ \leqq\ N\ \leqq\ 10^5 $ - $ 1\ \leqq\ t_i\ \leqq\ N $ - $ 1\ \leqq\ d_i\ \leqq\ 10^9 $ - 入力はすべて整数である。 ### Sample Explanation 1 寿司 $ 1,2,3 $ を食べた時、 - 「おいしさ基礎ポイント」は、$ 9+7+6=22 $ - 「種類ボーナスポイント」は、$ 2*2=4 $ で、得られる「満足ポイント」は $ 26 $ となり、これが最適です。 ### Sample Explanation 2 寿司 $ 1,2,3,4 $ を食べるのが最適です。 ### Sample Explanation 3 出力が $ 32 $ bit型整数に収まらない場合もあることに注意して下さい。