CF161B Discounts

超市进行优惠活动，顾客如果在一架购物车中放上一个凳子，他就可以半价买掉这架购物车里最便宜的商品（一架购物车中只能让一个东西半价）。 现在$\mathrm{Polycarpus}$要用$k$架购物车（容量无限，但不能有空车）装要买的$n$件商品，里面有一些是凳子。$\mathrm{Polycarpus}$希望用最少的钱来买这些东西。

无

无

在样例$1$中，购物车有$2$架，其中一架装商品$1$（凳子）和$2$（其他），另一架装商品$3$（凳子），这样安排便可以使价格最低。 对于$100\%$的数据，$1\leq n,k\leq 10^3$，$1\leq c_i\leq 10^9$，$1\leq t_i\leq 2$。