Maximize Sequence Sum with Intersection Constraints

You are given two sequences of n positive integers: \(\{a_i\}\) and \(\{b_i\}\) with indices \(1,2,\dots,n\). You must choose exactly \(K\) indices from each sequence. In other words, you need to select two increasing sequences of indices \(\{c_i\}\) and \(\{d_i\}\) satisfying

[ 1 \le c_1 < c_2 < \cdots < c_K \le n, \qquad 1 \le d_1 < d_2 < \cdots < d_K \le n, ]

with the additional requirement that at least \(L\) indices appear in both selections, i.e.,

[ \left|{c_1,c_2,\dots,c_K} \cap {d_1,d_2,\dots,d_K}\right| \ge L. ]

Your goal is to maximize the total sum of the elements corresponding to the selected indices, i.e.,

[ \sum_{i=1}^{K} a_{c_i} + \sum_{i=1}^{K} b_{d_i}. ]

Note: The selections for each sequence are independent except for the intersection constraint.

inputFormat

The first line contains three integers: n, K, and L.

The second line contains n integers representing the sequence \(\{a_i\}\).

The third line contains n integers representing the sequence \(\{b_i\}\).

outputFormat

Output a single integer, the maximum possible sum.

sample

3 1 0
1 2 3
3 2 1

6