#1844. [NOI2019] Sequence

[NOI2019] Sequence

Description

You are given two sequences {ai}\{a_i\} and {bi}\{b_i\} of length nn, and the element of them are indexed from 11 to nn. You need to choose KK numbers in each sequence, and ensure that at least LL positions are chosen in both sequences. Your task is to maximize the sum of the 2K2K numbers.

Formally speaking, you need to assign 22 sequences {ci}\{c_i\} and {di}\{d_i\} of length KK such that

  • 1c1<c2<<cKn1 \leq c_1 < c_2 < \cdots < c_K \leq n
  • 1d1<d2<<dKn1 \leq d_1 < d_2 < \cdots < d_K \leq n
  • $\left\lvert\{c_1, c_2, \cdots, c_K\} \cap \{d_1, d_2, \cdots, d_K\}\right\rvert \geq L$

Your goal is to maximize

i=1Kaci+i=1Kbdi\sum_{i=1}^{K}{a_{c_i}} + \sum_{i=1}^{K}{b_{d_i}}

Input

The first line contains a single integer TT — the number of test cases.

Each test case contains 33 lines.

The first line contains 33 integers n,K,Ln, K, L.

The second line contains nn integers a1,a2,,ana_1, a_2, \cdots, a_n.

The third line contains nn integers b1,b2,,bnb_1, b_2, \cdots, b_n.

Output

For each test case, print a single integer — the maximal sum.

Sample

5
1 1 1
7
7
3 2 1
4 1 2
1 4 2
5 2 1
4 5 5 8 4
2 1 7 2 7
6 4 1
1 5 8 3 2 4
2 6 9 3 1 7
7 5 4
1 6 6 6 5 9 1
9 5 3 9 1 4 2
14
12
27
45
62

For the first case, {ci}={di}={1}\{c_i\} = \{d_i\} = \{1\}.

For the second case, {ci}={1,3}\{c_i\} = \{1, 3\}, {di}={2,3}\{d_i\} = \{2, 3\}.

For the third case, {ci}={3,4}\{c_i\} = \{3, 4\}, {di}={3,5}\{d_i\} = \{3, 5\}.

For the fourth case, {ci}={di}={2,3,4,6}\{c_i\} = \{d_i\} = \{2, 3, 4, 6\}.

For the fifth case, {ci}={2,3,4,5,6}\{c_i\} = \{2, 3, 4, 5, 6\}, {di}={1,2,3,4,6}\{d_i\} = \{1, 2, 3, 4, 6\}.

Limits And Hints

For all of the tests, T10T \leq 10, 1n1061 \leq \sum{n} \leq 10^6, 1LKn2×1051 \leq L \leq K \leq n \leq 2 \times 10^5, 1ai,bi1091 \leq a_i, b_i \leq 10^9.

For partial scores, you can look up at the origin statement (NOI/2019/Day1.pdf).