SP132 HELPR2D2 - Help R2-D2!

在《星球大战》第三部曲中（传闻的标题是「我的维达之路」），R2-D2 再次肩负起一项繁重的任务，即用最快速度为共和国的运输飞船装载货物。设想一个巨大的空间区域，其中停泊着 $n$ 艘星际飞船。每艘飞船的容积为 $K$ 立方飞秒帕秒。各种容器 $C_i$ 依次到达，每个容器的体积为 $v_i$（单位为立方飞秒帕秒）。R2-D2 希望通过一种策略，尽量减少为这些容器所需的飞船数量。 尽管难题复杂，R2-D2 还是巧妙地选择了一种启发式算法。开始时，所有飞船均已准备好分配，并按编号为 $S_0, S_1, \ldots$ 排列。当某个容器 $C_j$ 到达时，他会选择最小编号且能够容纳此容器的飞船 $S_i$ 装载。在这种策略下，能够尽可能地减少在装载前容器的移动次数。 容器接连到达后，R2-D2 计算出用了多少艘飞船 $s$，并统计这个过程中总的空间浪费量 $w$。对于每艘飞船 $i=0, \ldots, s-1$，浪费量等于未使用的容量。 你的任务是模拟 R2-D2 所采用的这个装载算法。

第一行包含一个整数 $T$ ($T \leq 10$)，表示接下来有多少组测试数据。每组测试数据首先给出一行整数 $K$ ($K \leq 1000$)，表示每艘飞船的容量。接着第二行是整数 $n$ ($1 \leq n \leq 1000000$)，表示容器数量。接下来的行可以有两种形式：如果是一整数，则表示那时到来的容器的体积 $v_i$；如果以字符 `b` 开头，后跟两个整数 $r$ 和 $v$，则表示接下来 $r$ 个容器的体积均为 $v$。

对于每组测试数据，输出使用的飞船数量 $s$ 和总浪费量 $w$，二者以空格分隔。

可以假定所需的飞船数量最多为 100000，且 R2-D2 需要更换用于装载的飞船时不会超过 100000 次。 **本翻译由 AI 自动生成**