Description

Given two non-negative integers $n$ and $x$.

Also, for all $1 \le l \le r \le n$, an integer $w_{l,r}$ is given.

For an array of integers $A = [a_1, a_2, \ldots, a_n]$, define

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

You are required to find the maximum possible value of $f(A)$ over all arrays $A$ such that

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

Input Format

The input in this problem contains one or more test cases.

The first line contains a single integer $t$ -- the number of test cases ($1 \le t \le 50$).

The descriptions of the $t$ test cases follow.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 50$, $1 \le x \le 10^9$).

In the $i$-th of the following $n$ lines, there are $n - i + 1$ integers $w_{i,i}, \ldots, w_{i,n}$ ($1 \le w_{i,j} \le 10^6$).

Output Format

For each test case, output a single integer: the maximum value of $f(A)$ among all arrays $A$ such that

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

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