E. Hallway of Horrors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Hallway of Horrors is an infamous haunted house that consists of a single corridor filled with terrifying traps and surprises. Without fully understanding what he was getting into, Johnny entered the Hallway and encountered his first jumpscare. Now, he wants to leave, but he can only go forward, deeper into the Hallway of Horrors...

The Hallway of Horrors consists of a series of $$$n$$$ jumpscares in a row, where the jumpscare at index $$$i$$$ occurs once every $$$s_i$$$ timesteps — specifically when the time $$$t$$$ is a multiple of $$$s_i$$$ — with a scare value of $$$v_i$$$. Note that Johnny can experience the same jumpscare multiple times. Johnny starts at index $$$1$$$ at $$$t = 0$$$ having experienced the first jumpscare, and his goal is to reach the exit at index $$$n+1$$$. At every timestep, he can either move forward or stay still, but staying still will heighten Johnny's nerves, adding $$$w$$$ to Johnny's scare value.

Please help Johnny escape the Hallway of Horrors with the lowest cumulative scare value possible.

Input

The first line of input contains $$$n$$$ and $$$w$$$ ($$$1 \le n \le 10^3, 1 \le w \le 10$$$), the number of jumpscares and the scare value of staying still, respectively.

The second line contains $$$n$$$ integers, $$$s_1, s_2, ..., s_n$$$ ($$$1 \le s_i \le 10^3$$$), the period of repetition of each jumpscare.

The third line contains $$$n$$$ integers, $$$v_1, v_2, ..., v_n$$$ ($$$1 \le v_i \le 10$$$), the scare value of each jumpscare.

Output

The output should be one line containing the minimum possible scare value Johnny can accumulate by the time he reaches the exit.

Example
Input
3 1
2 1 2
1 2 3
Output
4
Note

Johnny starts with a scare value of $$$1$$$ from the first jumpscare at $$$t = 0$$$. Next, it is optimal to wait for one timestep at a cost of $$$1$$$, then move forward $$$3$$$ times, which will result in one jumpscare at index $$$2$$$. This gives a cumulative scare value of $$$1 + 1 + 2 = 4$$$.