P6646 [CCO 2020] Shopping Plans

有 $N$ 个商品，每个商品有个种类 $a_i$，有个价格 $c_i$。 对于第 $j$ 个种类，必须购买个数位于 $[x_j,y_j]$ 的商品，即最少购买 $x_j$ 个，最多购买 $y_j$ 个该种类的商品。 您需要求出前 $K$ 种便宜的方案所需的价钱，如果没有这样的方案，请输出 `-1`。 特别的，如果有相同钱数，但是具体方案不相同的，算作两种方案。

无

无

#### 样例解释 共有 $5$ 个商品，$2$ 种类型。 类型 $1$：$\{3,5,6\}$，类型 $2$：$\{1,3\}$。 类型 $1$ 与类型 $2$ 均只能选择一个商品。 对于最便宜的方案，选择 $\{1,3\}$ 即可。 以此类推。 #### 子任务 **本题使用捆绑测试** - Subtask 1（$20$ 分）：$x_j,y_j=1$，$N,M,K\le4\times 10^3$。 - Subtask 2（$20$ 分）：$x_j,y_j=1$，$N,M,c_i\le 4\times 10^3$。 - Subtask 3（$20$ 分）：$x_j,y_j=1$。 - Subtask 4（$20$ 分）：$x_j=0$。 - Subtask 5（$20$ 分）：无特殊限制。 对于 $100\%$ 的数据，保证 $1\le N,M,K\le 2\times 10^5$，$1\le a_i\le M$，$1\le c_i\le 10^9$，$0\le x_j\le y_j\le N$。 #### 说明 本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T3 Shopping Plans。 本题数据有所删减。