CF2174B.Wishing Cards

It is said that writing wishing cards on New Year's Eve can bring good luck. You have written wishing cards and plan to give them to Little A.

You have invited $n$ friends to help you deliver the wishing cards. You plan to give the $i$-th friend $b_i$ wishing cards. The friends will visit Little A's house in the order of $1$ to $n$, and each will hand over all his $b_i$ wishing cards to Little A. Little A always remembers the friend who gives her the most wishing cards, so after the $j$-th friend's visit, she gains happiness equal to the largest number of cards received so far, that is, $\max(b_1, b_2, \ldots, b_j)$.

The $i$-th friend can carry at most $a_i$ cards, and the total number of cards cannot exceed $k$. Your task is to optimally choose values of $b_i$ so that the total happiness of Little A after $n$ visits is maximized under these constraints.

Note that some friends may carry no cards at all, Little A won't get mad.

据说，除夕夜写贺卡能带来好运。你已经写好了贺卡，并计划将它们送给小A。

你邀请了 $n$ 位朋友来帮你递送贺卡。你计划给第 $i$ 位朋友 $b_i$ 张贺卡。朋友们将按编号 $1$ 至 $n$ 的顺序依次拜访小A的家，每位朋友会将其全部 $b_i$ 张贺卡交给小A。小A总是记得送给她贺卡数量最多的朋友，因此在第 $j$ 位朋友拜访之后，她获得的快乐值等于截至目前收到的最大贺卡数，即 $\max(b_1, b_2, \ldots, b_j)$。

第 $i$ 位朋友最多可携带 $a_i$ 张贺卡，且所有贺卡总数不能超过 $k$。你的任务是在满足这些约束的前提下，合理选择各 $b_i$ 的值，使得小A在 $n$ 次拜访结束后的总快乐值最大化。

注意：某些朋友可以不携带任何贺卡，小A不会生气。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le 360$), the number of friends, and the maximum total number of cards.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le k$), the maximum number of cards each friend can carry.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ and the sum of $k$ over all test cases does not exceed $1800$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 360$），分别表示朋友的数量以及卡片总数的上限。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le k$），表示每位朋友最多能携带的卡片数量。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$，且所有测试用例中 $k$ 的总和不超过 $1800$。

For each test case, output the maximum happiness Little A can get.

对于每个测试用例，输出小A能够获得的最大幸福值。

In the first test case, the only way to distribute wishing cards is $b = [0,0,1]$.

In the third test case, $b = [1,0,4]$ is invalid because you only have $k = 4$ wishing cards.

In the fourth test case, one of the optimal ways to distribute wishing cards is to set $b = [2,0,5,0,0]$, in which Little A will gain $2+2+5+5+5=19$ happiness.

在第一个测试用例中，分发许愿卡的唯一方式是 $b = [0,0,1]$。

在第三个测试用例中，$b = [1,0,4]$ 是无效的，因为你仅有 $k = 4$ 张许愿卡。

在第四个测试用例中，一种最优的许愿卡分配方式是令 $b = [2,0,5,0,0]$，此时小 A 将获得 $2+2+5+5+5=19$ 点幸福值。