描述

一列火车由一台机车牵引，机车后挂载多节旅客车厢。如果机车发生故障，火车将无法行驶。因此，铁路部门决定为每个车站配备三台小型机车。每台小型机车只能牵引少量旅客车厢。如果机车发生故障，三台小型机车无法牵引所有旅客车厢。因此，铁路部门制定了以下决策：

1.设定小型机车的最大牵引能力： 设定每台小型机车最多能牵引的旅客车厢数量，所有三台小型机车的牵引能力相同。 2.最大化运输乘客数量： 使用三台小型机车，将尽可能多的乘客运输到目的地。已知每节车厢的乘客数量，且乘客不允许在不同车厢之间移动。 3.牵引连续车厢： 每台小型机车必须牵引连续的旅客车厢。车厢编号从 1 开始。

例如，假设有 7 节客运车厢，一辆迷你机车最多可以拉动 2 节客运车厢。客车上的乘客人数从 1 到 7 依次为 35、40、50、10、30、45 和 60。

如果三辆小型机车拉动客运车厢 1-2、3-4 和 6-7，它们可以运送 240 名乘客。在此示例中，三辆小型机车不能运送超过 240 名乘客。

给定客运车厢的数量、每辆客运车厢的乘客人数以及微型机车可以牵引的最大客运车厢数量，编写一个程序来查找三个微型机车可以运送的最大乘客人数。

输入

输入的第一行包含一个整数 $t （1 <= t <= 11）$，即测试用例的数量，后跟每个测试用例的输入数据。每个测试用例的输入将如下所示： 输入文件的第一行包含客运车厢的数量，不会超过 $50,000$。第二行包含一个以空格分隔的整数列表，给出每节车厢中的乘客数，因此此行中的第$i$个数字是车厢$i$中的乘客数。没有一辆客车可容纳超过$100$ 名乘客。第三行包含单个微型机车可以牵引的最大客运车厢数量。这个数字不会超过客运车厢数量的$1/3$。

输出

每个测试用例应有一行，其中包含三个小型机车可以运输的最大乘客数量。

样例输入

1
7
35 40 50 10 30 45 60
2

样例输出

240

来源

2004 年德黑兰沙里夫大学预选赛