{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   The satisfaction is the sum of the \"base total deliciousness\" and the \"variety bonus\".\n*   The base total deliciousness is the sum of the deliciousness of the pieces you eat.\n*   The variety bonus is $x*x$, where $x$ is the number of different kinds of toppings of the pieces you eat.\n\nYou want to have as much satisfaction as possible. Find this maximum satisfaction."},{"iden":"constraints","content":"*   $1 \\leq K \\leq N \\leq 10^5$\n*   $1 \\leq t_i \\leq N$\n*   $1 \\leq d_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$t_1$ $d_1$\n$t_2$ $d_2$\n$.$\n$.$\n$.$\n$t_N$ $d_N$"},{"iden":"sample input 1","content":"5 3\n1 9\n1 7\n2 6\n2 5\n3 1"},{"iden":"sample output 1","content":"26\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."},{"iden":"sample input 2","content":"7 4\n1 1\n2 1\n3 1\n4 6\n4 5\n4 5\n4 5"},{"iden":"sample output 2","content":"25\n\nIt is optimal to eat Sushi $1,2,3$ and $4$."},{"iden":"sample input 3","content":"6 5\n5 1000000000\n2 990000000\n3 980000000\n6 970000000\n6 960000000\n4 950000000"},{"iden":"sample output 3","content":"4900000016\n\nNote that the output may not fit into a $32$\\-bit integer type."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}