output_description: Print the maximum satisfaction that you can obtain.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      t_1 d_1
      t_2 d_2
      .
      .
      .
      t_N d_N
attempt: #include<iostream>
  #include<queue>
  #include<vector>
  #include<map>
  #include<algorithm>
  using namespace std;
  typedef long long ll;
  typedef pair<ll, int> P;
  
  
  int main(){
    int N,K;
    cin >>N>>K;
    vector<pair<ll, ll>> list;
    
    for (int i=0;i<N;i++){
      int t, d;
      cin >> t>> d;
      P p=make_pair(t,d);
      list.push_back(p);
    }
  
    //queue は，今使っている寿司番号を格納している。
    priority_queue<pair<ll, int>> que;
    //countは，答えに，何が何個使われているかをcountしている。
    map<ll, int> count;
    //初期化しておく
    for (int i=0;i<N;i++){
      count[list[i][0]]=0;
    }
    
    ll bonus=0;
    ll delicious=0;
  
    //はじめの状態
    for (int i=0;i<K;i++){
      delicious+=list[i][1];
      P r=make_pair(list[i][1], i);
      que.push(r);
      count[list[i][0]]++;
      if (count[list[i][0]==1){
        bonus++;
      }
    }
  
    ll ans=pow(bonus, 2)+delicious;
  
    for (int i=K;i<N;i++){
      if (count[list[i+1][0]]==0){
        P r=que.top();
        int k=r.second
        int ans_2=pow(bonus+1, 2)+delicious-list[k][1]+list[i][1];
        if (ans_2>ans){
          count[list[i][0]]++;
          r=make_pair(list[i][1], i);
          que.pop();que.push(r);
          bonus++;
          delicious+=list[i][1]-list[k][1];
          count[list[k][0]]--;
          ans=pow(bonus, 2)+delicious;
        }
      }
    cout << ans;
    return 0;
    }
    
  
  
problem_description: Statement
  
  There are N pieces of sushi. Each piece has two parameters: "kind of topping"
  t_i and "deliciousness" d_i. You are choosing K among these N pieces to eat.
  Your "satisfaction" here will be calculated as follows:
  
    * The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
    * The base total deliciousness is the sum of the deliciousness of the pieces you eat.
    * The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.
  
  You want to have as much satisfaction as possible. Find this maximum
  satisfaction.
samples: [{"input": "5 3\n    1 9\n    1 7\n    2 6\n    2 5\n    3 1", "output": "26\n    \n\nIf you eat Sushi 1,2 and 3:\n\n  * The base total deliciousness is 9+7+6=22.\n  * The variety bonus is 2*2=4.\n\nThus, your satisfaction will be 26, which is optimal.\n\n* * *"}, {"input": "7 4\n    1 1\n    2 1\n    3 1\n    4 6\n    4 5\n    4 5\n    4 5", "output": "25\n    \n\nIt is optimal to eat Sushi 1,2,3 and 4.\n\n* * *"}, {"input": "6 5\n    5 1000000000\n    2 990000000\n    3 980000000\n    6 970000000\n    6 960000000\n    4 950000000", "output": "4900000016\n    \n\nNote that the output may not fit into a 32-bit integer type."}]