Block Game

题号：NC301119
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯正在玩方块小游戏，游戏中有一排 $n$ 个方块，每个方块上都有一个数字，此外，他还有一个写着数字 $k$ 的万能方块，游戏过程如下。

$\hspace{15pt}$ 小苯可以进行任意次（可以为 $0$ 次）以下操作：

$\hspace{23pt}\bullet\,$ 将万能方块从方块序列的最左侧插入，同时最右侧的第 $n$ 个方块会被挤出这一行，成为新的万能方块。

$\hspace{30pt}$ 形式化地，记开始时的序列为 $a'_1,a'_2, \dots, a'_n$ （初始时 $a'_i = a_i$ ），万能方块值为 $k'$ （初始时 $k'=k$ ），操作完成后序列变为 $k', a'_1, \dots, a'_{n-1}$ ，万能方块上的数字变为 $a'_n$ ，其他方块保持相对顺序整体右移一位。

$\hspace{15pt}$ 你的任务是计算出，按照最优方式经过若干次操作后，从左往右数第一个方块上的数字加上最终的万能方块上的数字的总和的最大值。

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示方块个数、初始的万能方块上的数字。
第二行输入  个整数 ，表示从左往右数第  个方块上写的数字。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最终：从左往右数第一个方块上的数字  万能方块上的数字之和的最大值。

示例1

输入

复制

2
6 5
1 2 3 3 2 1
5 3
1 1 1 1 1

输出

复制

6
4

说明

对于第一组测试数据，我们操作一次后，方块序列变为 ，此时万能方块变为 ，总和为  达到最大。可以证明不存在更优的答案。