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

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

对于一个整数数组 $A = [a_1, a_2, \dots, 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$ 中，$f(A)$ 的最大可能值：

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

输入格式

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

第一行包含一个整数 $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}, \dots, w_{i,n}$ ($1 \le w_{i,j} \le 10^6$)。

输出格式

对于每个测试用例，输出一个整数：在满足 $a_1 + a_2 + \dots + a_n = x$ 且 $a_i \ge 0$ 的所有数组 $A$ 中，$f(A)$ 的最大值。

样例

输入样例 1

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

输出样例 1

30
10
14999999995