时空限制

1S/512M

题目描述

有 $n$ 名同学，编号为 $1\sim n$，同学 $i$ 的分数为 $p_i$。

编号在区间 $[l_1,r_1]$ 的同学语文好，编号在区间 $[l_2,r_2]$ 的同学数学好。

现在 Jiangly 老师要从中选出 $m$ 名同学组成自己的战队，要求选出的 $m$ 名同学中至少有 $k_1$ 名同学语文好，至少有 $k_2$ 名同学数学好。

求选出的同学的总分数之和最大是多少。

格式

输入格式

第一行包含一个整数 $n$，表示同学的数量。

第二行包含 $n$ 个整数 $p_i$，表示每个同学的分数。

第三行包含四个整数 $l_1,r_1,l_2,r_2$，含义与题目描述相同。

第四行包含三个整数 $m,k_1,k_2$，含义与题目描述相同。

输出格式

如果不存在满足条件的选人方案，输出 $−1$。否则输出一个整数表示选出的同学的总分数之和的最大值。

样例

样例输入 #1

6
6 3 4 3 7 9
1 4 3 6
3 2 2

样例输出 #1

19

样例解释 #1

Jiangly 老师可以选择 $1,3,6$ 三名同学，其中同学 $1$ 和同学 $3$ 语文好，同学 $3$ 和同学 $6$ 数学好，总分数之和为 $6+4+9=19$。

数据规模

对于 $10\%$ 的数据，$n\leq 50$。

对于 $40\%$ 的数据，$n\leq 300$。

另有 $20\%$ 的数据，$l_2>r_1$。

对于 $100\%$ 的数据，$1\leq m\leq n\leq 10^6$，$1\leq p_i\leq 10^9$，$1\leq l_1\leq r_1\leq n$，$1\leq l_2\leq r_2\leq n$，$1\leq k_1,k_2\leq m$。