{"problem":{"name":"Various Sushi","description":{"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 ca","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc116_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc116_d","tags":[],"sample_group":[["5 3\n1 9\n1 7\n2 6\n2 5\n3 1","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."],["7 4\n1 1\n2 1\n3 1\n4 6\n4 5\n4 5\n4 5","25\n\nIt is optimal to eat Sushi $1,2,3$ and $4$."],["6 5\n5 1000000000\n2 990000000\n3 980000000\n6 970000000\n6 960000000\n4 950000000","4900000016\n\nNote that the output may not fit into a $32$\\-bit integer type."]],"created_at":"2026-03-03 11:01:14"}}