解题思路

收益是价值和加上类型数的平方，所以既要贵的花，也可能要更多类型。类型奖励不是线性的，需要枚举最终用了多少种。

若选了某个类型，最优解一定包含该类型里价值最大的那一朵，其余按价值从大到小再拿。因此每种花排好序后只需考虑前缀。
把所有类型按「该种最贵的一朵」从大到小排列。可以证明：存在最优解，其类型集合恰好是这个序列的某个前缀。
设前缀长度为 $C$ ，则这 $C$ 种各拿最贵的一朵，还要再拿 $r=k-C$ 朵，只能从这 $C$ 种剩下的花里选最大的 $r$ 朵。前缀里花的总数不足 $k$ 则不可行。
每多加入一种，把该种除最大朵以外的花放进大根堆；当前计入的 $r$ 朵用小根堆维护，使它始终是已解锁续选花中最大的 $r$ 朵。枚举 $C$ 取最大的 $S+C^{2}$ 。
常见假解：种类越多越好；直接取价值前 $k$ 大再加种类平方；用 int 累加（价值和可到 $10^{14}$ ，种类平方可到 $10^{10}$ ）。

题目内容

花店里摆着 $n$ 朵花。第 $i$ 朵花有一个类型 $t_i$ 和一个价值 $v_i$ 。

你必须恰好从中选出 $k$ 朵花做成一束。设这 $k$ 朵花的价值之和为 $S$ ，其中出现过的不同的类型个数为 $C$ ，则这束花的收益定义为

$S + C \times C$

请计算能得到的最大收益。

第一行两个正整数 $n$ 和 $k$ （ $1\le k\le n\le 10^{5}$ ），表示花的数量和必须选中的朵数。

第二行 $n$ 个整数 $t_1,t_2,\dots,t_n$ （ $1\le t_i\le 10^{9}$ ），表示每朵花的类型。

第三行 $n$ 个整数 $v_1,v_2,\dots,v_n$ （ $1\le v_i\le 10^{9}$ ），表示每朵花的价值。

输出一个整数，表示最大收益。

输入

3 2
1 1 2
5 3 4

输出

说明

最大为 $13$ 。

输入

3 2
1 1 2
100 99 1

输出

说明

两朵类型 $1$ 的价值和为 $199$ ，类型数 $1$ ，收益 $200$ 。若改拿类型 $2$ 那朵价值 $1$ 的花，类型数变成 $2$ ，收益只有 $105$ 。种类更多不一定更优。

选择提交后点击「开始AI分析」