说明

给定两个非负整数 $n$ 和 $x$。

此外，对于所有 $1 \le l \le r \le n$，给定一个整数 $w_{l, r}$。

对于整数数组 $A = [a_1, a_2, \ldots, a_n]$，定义

$$f(A) = \sum_{l=1}^{n} \sum_{r=l}^{n} w_{l, r} \cdot \min(a_l, a_{l+1}, \dots, a_r).$$

你需要求出在所有满足

$$a_1 + a_2 + \cdots + a_n = x \quad \text{且} \quad a_i \ge 0$$

的数组 $A$ 中，$f(A)$ 的最大可能值。

输入格式

本题的输入包含一个或多个测试用例。

第一行包含一个整数 $t$ —— 测试用例的数量（$1 \le t \le 50$）。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 50$，$1 \le x \le 10^9$）。

在接下来的 $n$ 行中，第 $i$ 行包含 $n - i + 1$ 个整数 $w_{i,i}, \ldots, w_{i,n}$（$1 \le w_{i,j} \le 10^6$）。

输出格式

对于每个测试用例，输出一个整数：在所有满足

$$a_1 + a_2 + \ldots + a_n = x \quad \text{且} \quad a_i \ge 0$$

的数组 $A$ 中，$f(A)$ 的最大值。

3
5 10
1 1 1 1 1
1 1 1 1
1 1 1
1 1
1
1 10
1
4 1000000000
1 2 3 4
5 6 7
8 9
10

30
10
14999999995

提示

翻译由 DeepSeek 完成