Problem Statement

There are NN pieces of sushi. Each piece has two parameters: "kind of topping" titi and "deliciousness" didi. You are choosing KK among these NN 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∗xx∗x, where xx 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.

Constraints

• 1≤K≤N≤1051≤K≤N≤105
• 1≤ti≤N1≤ti≤N
• 1≤di≤1091≤di≤109
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN KK
t1t1 d1d1
t2t2 d2d2
..
..
..
tNtN dNdN

Output

Print the maximum satisfaction that you can obtain.

---

Sample Input 1 Copy

Copy

5 3
1 9
1 7
2 6
2 5
3 1

Sample Output 1 Copy

Copy

26

If you eat Sushi 1,21,2 and 33:

• The base total deliciousness is 9+7+6=229+7+6=22.
• The variety bonus is 2∗2=42∗2=4.

Thus, your satisfaction will be 2626, which is optimal.

---

Sample Input 2 Copy

Copy

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Sample Output 2 Copy

Copy

25

It is optimal to eat Sushi 1,2,31,2,3 and 44.

---

Sample Input 3 Copy

Copy

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

Sample Output 3 Copy

Copy

4900000016

Note that the output may not fit into a 3232-bit integer type.

题意：给定N个结构体，每一个结构体有两个信息，分别是type  和 x，让你从中选出K个结构体，使之type的类型数的平方+sum{ xi } 最大。

思路：【贪心】将X从大到小排序，然后按顺序取前K个，在取前K个过程中，将已经出现的类型放入栈中。然后，开始遍历K+1----N的元素，使得不断加入没有出现的元素的类型。在此过程中通过弹栈更新最值。

AC代码：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 #define N 150000
 6 struct str{
 7     int x,y;
 8 }st[N];
 9 bool cmp(str a,str b){
10     return a.y>b.y;
11 }
12 map<int,int> mp;
13 stack<int> s;
14 signed  main(){
15     int n,k;
16     cin>>n>>k;
17     for(int i=1;i<=n;i++){
18         cin>>st[i].x>>st[i].y;
19     }
20     sort(st+1,st+1+n,cmp);
21     int maxn=0;
22     int type=0;
23     int sum=0;
24     for(int i=1;i<=k;i++){
25         if(!mp[st[i].x]){
26             mp[st[i].x]=1;
27             type++;
28         }else{
29             s.push(st[i].y);
30         }
31         sum+=st[i].y;
32         maxn=max(maxn,type*type+sum);    
33     }
34     for(int i=k+1;i<=n;i++){
35         if(s.empty())
36             break;
37         if(mp[st[i].x])
38             continue;
39         mp[st[i].x]=1;
40         type++;
41         sum-=s.top();
42         s.pop();
43         sum+=st[i].y;
44         maxn=max(maxn,type*type+sum);    
45     }
46     cout<<maxn;
47     return 0;
48 }