题目描述

徐老师会给定长为 $n$ 的两个序列 $a$ 和 $b$，以及两个整数 $p$ 和 $q$。

你需要选择若干个区间 $[l_i,r_i]$ 满足以下条件（令 $k$ 为你选择的区间数量）：

1. 对于所有 $i$ 满足 $1\le i\le k$，都有 $1\le l_i\le r_i\le n$ 以及 $p\le r_i-l_i+1\le q$。
2. 对于所有 $i,j$ 满足 $1\le i<j\le n$，都有 $r_i<l_j$ 或者 $l_i>r_j$。换句话说，任意两个区间是不相交的（端点相交也算相交）。
3. 对于所有 $i,j$ 满足 $1\le i\le k,l_i\le j\le r_i$，都有 $\sum_{t=l_i}^j b_t\ge 0$。换句话说，对于所有区间的所有前缀，其对应的 $b$ 之和均非负。

现在徐老师认为一个区间 $[l,r]$ 的权值为 $f(l,r)=\sum_{i=l}^r a_i$ 。

他需要你对于所有可能的选择方案，找出 $\sum_{i=1}^kf(l_i,r_i)$ 的最大值。

输入格式

第一行包含三个整数 $n,p,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

输出一行一个整数表示最大的 $\sum_{i=1}^kf(l_i,r_i)$。

数据范围

对于所有数据，满足 $1\le p\le q\le n\le 5\times 10^5$，$-2\times 10^5\le a_i,b_i\le 2\times 10^5$。

样例输入1

6 2 3
1 5 2 3 -4 3
3 -3 -1 2 -1 2

样例输出1

8

样例解释1

选择区间 $[1,2]$ 和 $[4,6]$，答案为 $(1+5)+(3-4+3)=8$。选择区间 $[1,2]$ 和 $[4,4]$ 是不合法的，因为区间 $[4,4]$ 长度为 $4-4+1=1 < p$。选择区间 $[1,2]$ 和 $[3,4]$ 也是不合法的，因为区间 $[3,4]$ 的一个前缀 $[3,3]$ 对应的 $b$ 之和为 $-1 < 0$。

样例输入2

13 3 4
1 5 2 3 5 1 2 3 4 2 3 1 5
1 2 -3 -1 3 -1 -2 1 0 3 -2 1 -1

样例输出2

30