P15316 [VKOSHP 2025] Strange Sum

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. $$

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$).

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. $$