P15316 [VKOSHP 2025] Strange Sum

给定两个非负整数 $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)$ 的最大值。

翻译由 DeepSeek 完成