CF2174B Wishing Cards

据说在除夕夜写下心愿卡能带来好运。你已经写好了心愿卡，打算送给 Little A。 你邀请了 $n$ 位朋友帮你送心愿卡。你计划让第 $i$ 位朋友带 $b_i$ 张心愿卡。朋友们将依次以 $1$ 到 $n$ 的顺序拜访 Little A，每个人会把自己全部的 $b_i$ 张心愿卡交给 Little A。Little A 会记住送她心愿卡最多的那位朋友，所以在第 $j$ 位朋友拜访之后，她会获得等于当前收到的最多卡片数量的幸福值，即 $\max(b_1, b_2, \ldots, b_j)$。 第 $i$ 位朋友最多能携带 $a_i$ 张卡片，并且总共送出的卡片数不能超过 $k$。你的任务是在以上约束下，最优地选择每个人带卡片的数量 $b_i$，使得 $n$ 次拜访后 Little A 获得的总幸福值最大。 注意，有些朋友可以一张卡片也不带，Little A 并不会因此生气。

每组测试包含多个测试用例。第一行包含测试用例数量 $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 \times 10^5$，所有测试用例中的 $k$ 总和不超过 $1800$。

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

在第一个测试用例中，唯一的分配方式是 $b = [0,0,1]$。 在第三个测试用例中，$b = [1,0,4]$ 不合法，因为你只有 $k=4$ 张心愿卡。 在第四个测试用例中，一种最优分配方式是 $b = [2,0,5,0,0]$，这样 Little A 会获得 $2+2+5+5+5=19$ 的幸福值。 由 ChatGPT 5 翻译