C. Nest Robbing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are on the hunt for some tasty dino eggs! There are $$$n$$$ dinosaur nests belonging to $$$m$$$ unique species lined up in a row. Each nest belongs to a species $$$s_i$$$ and has an egg with weight $$$w_i$$$. Your bag can hold no more than $$$k$$$ eggs. In order to preserve species $$$\textit{diversity}$$$, you will not take eggs from the same species more than $$$x$$$ times. In order to prevent a species from becoming $$$\textit{invasive}$$$, you must take at least 1 egg from each species. Find the maximum total weight of eggs you can steal!

Input

The first line of input will contain four integers $$$n$$$ $$$m$$$ $$$k$$$ $$$x$$$, defined below:

  • $$$n$$$ $$$(1 \leq n \leq 10^5)$$$: the number of nests
  • $$$m$$$ $$$(1 \leq m \leq n)$$$: the number of unique species
  • $$$k$$$ $$$(m \leq k \leq n)$$$: the capacity of your bag
  • $$$x$$$ $$$(1 \leq x \leq n)$$$: the maximum number of eggs from a single species you can collect

The second line of input will consist of $$$n$$$ integers, where the $$$i$$$-th integer is $$$s_i$$$ $$$(1 \leq s_i \leq m)$$$, denoting the species of the $$$i$$$-th nest.

The third line of input will consist of $$$n$$$ integers, where the $$$i$$$-th integer is $$$w_i$$$ $$$(1 \leq w_i \leq 10^5)$$$, denoting the weight of the $$$i$$$-th nest's egg.

Output

Output a single integer, the maximum total weight of eggs you can collect.

Examples
Input
5 2 5 2
1 1 2 2 2
1 2 3 4 5
Output
12
Input
8 3 4 2
1 2 3 1 2 3 1 2
9 1 2 8 3 4 7 5
Output
26
Note

In the first test case, you want to take both of the eggs of species type 1, and the eggs weighted 5 and 4 from species type 2. This sums up to 12. Note that you do not have to fill your bag's capacity.

In the second test case, you should take the eggs with weights 9, 8, 5, and 4.