Strange Partition

题意翻译

### 题目描述 给定一个长度为 $n$ 的数组 $a$ 和 一个整数 $x$，可以进行任意多次以下操作：将当前数组中 **相邻** 的两个数用他们的 **和** 替换掉。 定义一个长度为 $k$ 的数组 $b$ 的美丽度是： $$\sum\limits_{i=1}^k{\lceil\frac{b_i}{x}\rceil}$$ 现在求能对原数组经过若干次变换得到的数组的 **最小美丽度** 和 **最大美丽度** ### 输入格式 第一行一个整数 $T$ ，表示 $T$ 组数据。 每组数据： 第一行两个整数 $n,x$ 第二行 $n$ 个整数表示 $a$ 数据保证： * $\sum {n} \leq 10^5$ * $a_i, x \leq 10^9$ * $T \leq 1000$ ### 输出格式 共 $T$ 行，每行两个数，分别表示题面中的 **最小美丽度** 和 **最大美丽度**。

题目描述

You are given an array $ a $ of length $ n $ , and an integer $ x $ . You can perform the following operation as many times as you would like (possibly zero): replace two adjacent elements of the array by their sum. For example, if the initial array was $ [3, 6, 9] $ , in a single operation one can replace the last two elements by their sum, yielding an array $ [3, 15] $ , or replace the first two elements to get an array $ [9, 9] $ . Note that the size of the array decreases after each operation. The beauty of an array $ b=[b_1, \ldots, b_k] $ is defined as $ \sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil $ , which means that we divide each element by $ x $ , round it up to the nearest integer, and sum up the resulting values. For example, if $ x = 3 $ , and the array is $ [4, 11, 6] $ , the beauty of the array is equal to $ \left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8 $ . Please determine the minimum and the maximum beauty you can get by performing some operations on the original array.

输入输出格式

输入格式

The first input line contains a single integer $ t $ — the number of test cases ( $ 1 \le t \le 1000 $ ). The first line of each test case contains two integers $ n $ and $ x $ ( $ 1 \leq n \leq 10^5 $ , $ 1 \leq x \leq 10^9 $ ). The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ), the elements of the array $ a $ . It is guaranteed that the sum of values of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case output two integers — the minimal and the maximal possible beauty.

输入输出样例

输入样例 #1

2
3 3
3 6 9
3 3
6 4 11

输出样例 #1

6 6
7 8

说明

In the first test case the beauty of the array does not change if we perform any operations. In the second example we can leave the array unchanged to attain the maximum beauty, and to get the minimum beauty one can replace two elements $ 4 $ and $ 11 $ with their sum, yielding an array $ [6, 15] $ , which has its beauty equal to $ 7 $ .