N. Necklace
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Isaac joined a group of tourists walking by the Agua Azul park in Guadalajara, he was listening to some guides who said that Guadalajara is also called a pearl in the desert. He was wondering why would it be called that way.

So, he continued walking and found a magical pearl necklace! The necklace is conformed by two types of pearls.

  • Type 1 pearls: allow you to gain $$$a_i$$$ points.
  • Type 2 pearls: allow you to exchange $$$a_i$$$ points for $$$a_i$$$ coins.

Isaac doesn't want to be greedy, so he decided to take at most $$$K$$$ pearls from the necklace, but he can't take pearls without cutting the necklace to remove them. So he decided to cut the necklace at some point and then take pearls from either side starting from it. Each time that Isaac takes a pearl from any of the sides, he can only take the pearl that is on the front of the side at that moment.

He can only take type 2 pearls if he has enough points to immediately exchange them for coins.

Help Isaac know what is the maximum amount of coins he can get!

Input

The first line of input contains two integers separated by a space $$$N$$$ and $$$K$$$ $$$\left(1 \leq N \leq 10^5, 1 \leq K \leq 100\right)$$$, representing the number of pearls in the necklace, and the maximum number of pearls Isaac will take from the necklace.

The second line of input contains $$$N$$$ integers, representing each of the $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) values of each pearl in the necklace.

The third and las line contains $$$N$$$ integer numbers, representing the type $$$1$$$ or $$$2$$$ of the pearl in each position of the necklace.

Output

Print a line with a single integer number, the maximum amount of coins Isaac can get from the necklace.

Examples
Input
2 2
1 1
1 2
Output
1
Input
6 4
2 2 4 4 6 1
1 2 1 1 2 1
Output
8