题目内容

在物流仓库中，有 $n$ 种不同类型的包裹，第 $i$ 种包裹的数量为 $a_i$。现在需要将所有包裹全部分配给 $k$ 名快递员，每种包裹必须恰好分完。为了体现公平，对于任意一种包裹，任意两名快递员分得的该种包裹的数量之差不得超过 $1$。

容易看出，对于第 $i$ 种包裹，唯一的分配方式是：每名快递员先得到 $\lfloor a_i/k \rfloor$ 个，剩余的 $a_i \bmod k$ 个包裹再分别分给 $a_i \bmod k$ 名不同的快递员，每人多拿 $1$ 个。因此，在任意一种合法的全部分配方案中，一名特定的快递员可能获得的包裹总数的最小值为 $\sum_{i=1}^{n} \lfloor a_i/k \rfloor$，最大值则为 $\sum_{i=1}^{n} \lceil a_i/k \rceil$。

请你对于每组数据，输出任意一名快递员所能获得的包裹总数的最小值与最大值。

数据范围与约束：

• 测试数据组数 $T$ 满足 $1 \le T \le 2 \times 10^5$。
• 对于每组数据，包裹种类数 $n$ 满足 $1 \le n \le 2 \times 10^5$，快递员人数 $k$ 满足 $1 \le k \le 10^9$。
• 每种包裹的数量 $a_i$ 满足 $0 \le a_i \le 10^9$。
• 保证所有测试数据的 $n$ 总和不超过 $5 \times 10^5$。

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$)，表示测试数据组数。接下来每组数据按以下格式给出： 第一行包含两个整数 $n$ ($1 \le n \le 2 \times 10^5$) 和 $k$ ($1 \le k \le 10^9$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

输出描述

对于每组测试数据，输出一行两个整数，分别表示任意一名快递员可能获得的包裹总数的最小值与最大值，中间用空格分隔。

样例1

输入

2
3 3
5 5 5
3 1
100 200 300

输出

3 6
600 600

说明

第一组数据：$n=3$，$k=3$，包裹数量分别为 5、5、5。对于每种包裹，每名快递员先获得 $\lfloor 5/3 \rfloor = 1$ 个，剩余 $5 \bmod 3 = 2$ 个再分给 2 名不同的快递员，每人多 1 个。因此，对于第 $i$ 种包裹，一名快递员最少获得 1 个，最多获得 2 个。总共有 3 种包裹，所以包裹总数的最小值为 $1+1+1=3$，最大值为 $2+2+2=6$。

第二组数据：$n=3$，$k=1$，包裹数量为 100、200、300。只有 1 名快递员，他必须拿走所有包裹，因此最小值和最大值均为所有包裹数量之和：$100+200+300=600$。

样例2

输入

1
4 5
0 10 0 3

输出

2 3

说明

该组数据中 $n=4$，$k=5$，包裹数量分别为 0、10、0、3。

• 对于数量为 0 的包裹：$\lfloor 0/5 \rfloor = 0$，$\lceil 0/5 \rceil = 0$。
• 对于数量为 10 的包裹：$\lfloor 10/5 \rfloor = 2$，且 $10 \bmod 5 = 0$，因此上取整也为 2。每名快递员固定获得 2 个该种包裹。
• 对于数量为 3 的包裹：$\lfloor 3/5 \rfloor = 0$，剩余 $3$ 个包裹分给 3 名快递员，有人得 1 个，有人得 0 个。故该种包裹最少得 0 个，最多得 1 个。

将所有种类的最小值相加：$0+2+0+0=2$；最大值相加：$0+2+0+1=3$。因此输出 2 3。

样例3

输入

1
2 100
10 5

输出

0 2

说明

该组数据中 $n=2$，$k=100$，包裹数量为 10 和 5，均小于 $k$。

• 对于数量为 10 的包裹：$\lfloor 10/100 \rfloor = 0$，剩余 10 个包裹分给 10 名快递员，有人得 1 个，有人得 0 个，因此最少 0，最多 1。
• 对于数量为 5 的包裹同理，最少 0，最多 1。

所以一名快递员最少获得 $0+0=0$ 个包裹，最多获得 $1+1=2$ 个包裹。