读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：packing.in

输出：packing.out

题目描述

给定 $n$ 个物品，第 $i$ 个物品体积为 $a_i$。你需要按输入顺序将它们装入容量均为 $C$ 的箱子中。

请分别实现以下两种经典近似算法，并输出各自使用的箱子数量：

• First Fit（首次适应）：按顺序处理物品，把当前物品放入编号最小且还能容纳它的已有箱子；若不存在则新开一个箱子。
• Best Fit（最佳适应）：按顺序处理物品，把当前物品放入所有可容纳它的箱子中“剩余空间最小”的那个；若不存在则新开一个箱子。

输入格式

第一行一个整数 $T$，表示测试组数。

对于每组数据：

• 第一行两个整数 $n,C$；
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

保证 $1 \le a_i \le C$，且所有测试组的 $n$ 之和不超过 $10^6$。

输出格式

对每组数据输出一行两个整数，依次表示 First Fit 与 Best Fit 使用的箱子数。

输入输出样例

2
2 2
1 1
5 10
5 8 2 5 9

1 1
4 3

说明/提示

数据范围：$1 \le T$，$1 \le n \le 10^6$，$1 \le C \le 10^9$，且所有测试组的 $n$ 之和不超过 $10^6$。