据说除夕夜写许愿卡可以带来好运。你写好了愿望卡,打算送给小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不会生气。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出小A可以获得的最大幸福感。
示例
输入复制
43 40 0 16 81 2 0 5 1 83 41 0 45 82 4 5 4 3
输出复制
120519
注意
在第一个测试用例中,分发许愿卡的唯一方法是$$$b = [0,0,1]$$$。
在第三个测试用例中,$$$b = [1,0,4]$$$ 无效,因为您只有 $$$k = 4$$$ 许愿卡。
在第四个测试用例中,分发许愿卡的最佳方式之一是设置$$$b = [2,0,5,0,0]$$$,这样小A将获得$$$2+2+5+5+5=19$$$的幸福感。