C. [Algo Beat Contest 005 C] 玉馔逢市

赠品就是礼品吗？

给定一个长度为 的正整数序列 。你需要将序列 划分为三个连续段（允许某些段为空），设它们的和分别为 。

划分需满足以下条件：

1. 必须是序列的前缀和，即存在一个 满足 。
2. 必须是三者中的最小值，即 且 。
3. 将 按升序排序得到 ，需满足相邻元素之差不超过 ： 且 。

现有 位同学购买套餐，共有三种套餐，分别对应价值 。每种套餐最多被购买 次。每位同学都会选择当前可选的价值最大的套餐。

请问是否存在合法的划分方案，使得 位同学都能买到套餐？若存在，输出 位同学获得的价值总和的最大值；否则输出 。

第一行依次输入四个整数 。

接下来的一行，输入 个整数，第 个数表示 。

若没有一种合法方案使满足上述条件的情况下使 位同学都购买到套餐，则输出 。

否则输出一个整数表示 位同学得到的礼品价值和的最大值。

输入 #1

3 10 2 4
10 20 30 

输出 #1

100

输入 #2

3 10 1 4
10 20 30

输出 #2

-1

输入 #3

5 0 2 4
10 30 20 20 40

输出 #3

160

【样例 1 解释】

有一种合法划分方案，三个连续段分别为 。此时 位同学得到的套餐价值和最多为 。可以证明，此时为最优的。

【样例 2 解释】

显然地，每种套餐只允许 人购买。对于每种方案，总是有 位同学最后会买不到套餐。

【样例 3 解释】

有一种合法划分方案，三个连续段分别为 。此时 位同学得到的套餐价值和最多为 。可以证明，此时为最优的。

【数据范围】

「本题采用捆绑测试」

对于所有的数据，满足:

• 。

• 。

• 。

Subtask #0 为样例，占 分。

• 特殊性质 A：保证 。

• 特殊性质 B：保证 。