该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

B.百亿补贴

你想要购买 $n$ 个不同的物品，其中有一些物品参加了百亿补贴优惠。

有 $k$ 次下单机会，每一单可以购买任意个物品。每一单中如果有至少一个物品参加了百亿补贴优惠，则本单中最便宜的物品可以享受半价优惠。

你想通过 $k$ 次下单把每个物品各买恰好一次。请计算最小的开销。

输入格式

第一行两个正整数 $n$ 和 $k$。

接下来 $n$ 行，每行两个整数 $p$ 和 $t$。$p$ 是该物品价格，$t$ 是该物品种类，如果是 $t=1$ 则该物品参加了百亿补贴优惠。

输出格式

一行，表示最少的花费。

样例输入1

3 2
20 1
40 1
20 0

样例输出1

50

样例解释

第一次只买第2个物品，花费40*0.5=20

第二次买第1、3个物品，花费20+20*0.5=30

一共花了50

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 20$。

对于额外 $30\%$ 的数据，有 $k=2$。

对于所有数据，有 $1 \leq k \leq n \leq 10^5$。物品价格是不超过 $10 ^ 9$ 的偶数。