SP12236 CLOUDMG - Cloud Computing

随着云计算概念的普及，IaaS（基础设施即服务）模式也越来越流行。在这种模式下，可以通过互联网租用和管理服务器。 Cloud, Inc. 是一家提供 IaaS 服务的公司，他们正在为客户设计一个新的数据中心。经过研究发现，客户总共需要 $K$ 台服务器，每台服务器必须能够承受一定的需求级别。假设服务器的成本是随着它可以处理的需求增加而变高的，从成本角度来看，最理想的方案是为每个客户量身定制 $K$ 台服务器以精确满足其需求。 然而，数据中心中有 $K$ 种不同硬件配置对于管理员来说是个大麻烦。为简化管理，要求所购服务器的类型不超过 $L$ 种。满足需求 $c$ 的服务器也可以满足比 $c$ 小的任何需求。 一个简单的方法是只购买一种可以满足最高需求的服务器，因为这样也能覆盖所有较低的需求。但此方案的成本也许会过于高昂。在允许最多购买 $L$ 种不同类型服务器的前提下，可能会有更优的选择。例如，有 3 个客户的需求分别是 3、7 和 16。假设满足需求 3 的服务器成本是 1500 雷亚尔，满足需求 7 的服务器成本是 5500 雷亚尔，而满足需求 16 的服器成本是 19200 雷亚尔。如果最多购买 2 种类型的服务器来满足所有客户，你有以下选择： - 购买三台容量为 16 的服务器，总成本为 57600 雷亚尔； - 购买两台容量为 16 的服务器和一台容量为 7 的，总成本为 43900 雷亚尔； - 购买两台容量为 16 的服务器和一台容量为 3 的，总成本为 39900 雷亚尔； - 购买一台容量为 16 的服务器和两台容量为 7 的，总成本为 30200 雷亚尔。 在这些选项中，最后一种方案的总成本最低。 你将得到客户的 $K$ 个需求以及满足这些需求的服务器类型价格。请计算出购买 $K$ 台服务器的最低总成本，同时保证购买的服务器类型不超过 $L$ 种。 ### 注意事项 - 每台服务器只能供一个客户使用。比如，一台容量为 4 的服务器不能同时供两位需求各为 2 的客户使用。 - 设 $D_i$ 和 $D_j$ 为两个需求，且 $P_i$ 和 $P_j$ 为满足这些需求服务器的价格。如果 $D_i < D_j$，则 $P_i < P_j$。

- 输入包含多组测试用例 - 每个测试用例以两整数 $K$ 和 $L$ 开始，表示需要购买的服务器数量和允许的最大服务器种类数（$1 \leq L \leq K \leq 10^5$）。 - 接下来有 $K$ 行，每行包含两个整数 $D_i$ 和 $P_i$，表示第 $i$ 个需求和与其匹配服务器的价格（$1 \leq D_i, P_i \leq 10^6$）。 - 当 $K = L = 0$ 时结束输入，这组数据不需处理。

- 对于每个测试用例，输出一个整数 $T$，表示获取最低总成本。 ## 示例 输入： ``` 10 3 1 1 2 4 3 5 4 7 5 8 6 12 7 13 8 18 9 19 10 21 0 0 ``` 输出： ``` 129 ``` 最优方案是购买3种类型的服务器来满足需求： - 购买3台容量为10的服务器满足需求10、9和8； - 购买2台容量为7的服务器满足需求7和6； - 购买5台容量为5的服务器满足其他需求。 总花费为 $3 \times 21 + 2 \times 13 + 5 \times 8 = 129$. **本翻译由 AI 自动生成**