Ray and his subordinates, Jay and May, are planning to overthrow AUCPL and rename it Ray-UCPL. As part of this effort, Ray has assigned them the task of replacing every AUCPL logo with a new logo featuring his likeness. Each logo has an importance value - higher values indicate more important logos to replace.

Ray has created a list of all AUCPL logos and their importance values. Jay and May work through the list from beginning to end, never skipping a logo. Ray makes exactly ~k~ assignments, each sending either Jay or May to process the next unprocessed block. Jay processes the next ~b_j~ logos, while May processes the next ~b_m~ logos.

Jay is fast, but sometimes fails to replace a logo correctly. May is slower, but always replaces her logos correctly.

Ray and co. have limited time, so they cannot replace every logo. Even if Jay is assigned all ~k~ times, only ~k \cdot b_j < n~ logos are processed.

Input

The first line contains four integers ~n~, ~k~, ~b_j~, and ~b_m~: the number of logos, the number of assignments, and the number of logos Jay and May process per assignment, respectively. ~1 \leq n, k \leq 1000~, ~1 \leq b_m < b_j \leq 1000~, and ~k \cdot b_j < n~.

The next line contains ~n~ integers ~x_1, x_2, \dots, x_n~, the importance values of the logos from front to back. ~1 \leq x_i \leq 10^{5}~.

The next line contains ~n~ integers ~y_1, y_2, \dots, y_n~, each equal to ~0~ or ~1~. If Jay is assigned logo ~i~, he successfully replaces it exactly when ~y_i = 1~. A failed replacement contributes zero importance, but the logo is still processed.

Output

Output the maximum possible sum of importance values of successfully replaced logos.

Examples

Input 1

7 3 2 1
4 8 1 3 4 4 2
0 1 1 0 0 1 0

Output 1

16

Assign in the order May, Jay, May. May replaces logos worth ~4~, Jay successfully replaces logos worth ~8 + 1~, and May then replaces a logo worth ~3~, for a total of ~16~.

Input 2

7 3 2 1
4 8 1 3 4 4 2
0 0 0 0 0 0 0

Output 2

13

Assign in the order May, May, May. May replaces logos worth ~4~, then ~8~, then ~1~, for a total of ~13~.