给定两个非负整数 $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},\ldots,a_r)$$

要求在所有满足

$$a_1+a_2+\cdots+a_n=x,\qquad a_i\ge 0$$

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

输入格式

本题包含一组或多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数：

$$1\le t\le 50$$

接下来是 $t$ 组数据。

每组数据第一行包含两个整数 $n,x$：

$$1\le n\le 50,\qquad 1\le x\le 10^9$$

接下来 $n$ 行。第 $i$ 行包含 $n-i+1$ 个整数：

$$w_{i,i},w_{i,i+1},\ldots,w_{i,n}$$

其中：

$$1\le w_{i,j}\le 10^6$$

输出格式

对每组测试数据，输出一个整数，表示满足条件的数组 $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