AT_nikkei2019_qual_f Jewels

你有 $n$ 个物品，每个物品有一个颜色 $c_i (1 ≤ c_i ≤ K)$ 和权值 $v_i$。你需要选出 $x$ 个物品，满足若颜色 $i$ 的物品被选中，那么颜色 $i$ 至少存在两个物品被选中，并且最大化总权值和。你需要对 $x = 1\dots n$ 均求出答案。如果无解，则输出 $-1$ 。

输入第一行两个 $n$， $K$。 接下来 $n$ 行，每行两个整数 $c_i$， $v_i$。

输出共 $n$ 行，每 $i$ 行表示 $x =$ i 时的答案。若无解，输出 $-1$。

对于所有数据， $1 ≤ n ≤ 2 \times 10^5, 1 ≤ K ≤\frac n 2,1\le c_i\le K, 0 \le v_i \le 10^9$ ,保证对于每种出现在了输入中的颜色，至少存在 $2$ 个该颜色的物品。