#P15853. [Roi2025 Team]Strange Sum / 奇怪的和

[Roi2025 Team]Strange Sum / 奇怪的和

给定两个非负整数 nn 和 xx。

同时,对于所有 1≤l≤r≤n1\le l\le r\le n,给定整数 wl,rw_{l,r}。

对于整数数组

A=[a1,a2,…,an]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)$$

要求在所有满足

a1+a2+⋯+an=x,ai≥0a_1+a_2+\cdots+a_n=x,\qquad a_i\ge 0

的数组 AA 中,求 f(A)f(A) 的最大可能值。

输入格式

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

第一行包含一个整数 tt,表示测试数据组数:

1≤t≤501\le t\le 50

接下来是 tt 组数据。

每组数据第一行包含两个整数 n,xn,x:

1≤n≤50,1≤x≤1091\le n\le 50,\qquad 1\le x\le 10^9

接下来 nn 行。第 ii 行包含 n−i+1n-i+1 个整数:

wi,i,wi,i+1,…,wi,nw_{i,i},w_{i,i+1},\ldots,w_{i,n}

其中:

1≤wi,j≤1061\le w_{i,j}\le 10^6

输出格式

对每组测试数据,输出一个整数,表示满足条件的数组 AA 中 f(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