I. Perils and Patrols
time limit per test
6 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

Alice has recently been appointed as the commander of a mercenary guild in the dangerous realm of Iron Escort. Her first contract requires her to travel safely through $$$N$$$ consecutive regions in order, from region $$$1$$$ to region $$$N$$$, but the roads are treacherous.

Alice starts her journey alone, with $$$0$$$ guards. Before stepping into any region, she evaluates her current party size, let's denote it as $$$u$$$, and decides on a new party size, $$$v$$$. Due to logistical constraints, she can adjust her party size by at most $$$K$$$ guards at a time. This means the absolute difference between $$$u$$$ and $$$v$$$ cannot exceed $$$K$$$, and her party size $$$v$$$ can never be negative.

Managing her escort party requires spending coins:

  • Alice pays a hiring fee of $$$H$$$ coins for every new guard she hires.
  • Alice pays a wage of $$$S$$$ coins to every guard currently in her newly chosen party of $$$v$$$.

If Alice decides to dismiss guards to reach her new party size, she receives no refunds, but she successfully avoids paying wages for those dismissed individuals. Overall, her total logistical cost before entering a region is exactly $$$H \cdot \max(0, v - u) + S \cdot v$$$.

Once the logistics are settled and wages are paid, Alice's party steps into the $$$i$$$-th region. Danger strikes immediately upon crossing the border, where the party faces the region's innate danger level, $$$D_i$$$. If Alice's chosen guard count $$$v$$$ is strictly less than $$$D_i$$$, bandits ambush the under-protected caravan, forcing her to pay a steep penalty of $$$P_i \cdot (D_i - v)$$$ coins, dictated by the region's specific ambush penalty multiplier, $$$P_i$$$.

After surviving the initial perils of the border, the party must travel deeper into the local warlord's territory. These warlords are fiercely territorial and strictly enforce a martial limit, $$$M_i$$$, refusing to let massive private armies freely roam their lands. If Alice's party arrives at these checkpoints with a guard count exceeding $$$M_i$$$, the local forces permanently confiscate the excess guards without offering any compensation. This abruptly forces her party size down to exactly $$$M_i$$$ guards before she can proceed to the next region, whereas a smaller party is allowed to pass with its numbers intact.

Help Alice find the minimum total number of coins she needs to spend to successfully complete her contract and travel through all $$$N$$$ regions.

Input

The first line of the input contains four integers $$$N$$$, $$$K$$$, $$$H$$$, and $$$S$$$ $$$(1 \le N \le 10^5$$$, $$$0 \le K, H, S \le 10^4)$$$ — the number of regions, the maximum change in guards allowed per step, the hiring cost, and the wage, respectively.

The second line contains $$$N$$$ integers $$$D_1, D_2, \dots, D_N$$$ $$$(0 \le D_i \le 2000)$$$ — the danger levels of the regions.

The third line contains $$$N$$$ integers $$$P_1, P_2, \dots, P_N$$$ $$$(0 \le P_i \le 10^4)$$$ — the ambush penalty multipliers.

The fourth line contains $$$N$$$ integers $$$M_1, M_2, \dots, M_N$$$ $$$(0 \le M_i \le 2000)$$$ — the martial limits of the regions.

Output

Print a single integer denoting the minimum number of coins Alice must spend to complete her journey.

Example
Input
2 5 10 5
3 2
100 100
1 2
Output
65
Note

In the first step, Alice starts with $$$0$$$ guards. Before entering the first region, she chooses to hire $$$3$$$ guards. She pays a hiring fee of $$$30$$$ coins and a wage of $$$15$$$ coins. Her guard count $$$v = 3$$$ exactly matches the danger level $$$D_1 = 3$$$, so she avoids the massive ambush penalty. However, the martial limit for this region is $$$M_1 = 1$$$. Because her party size of $$$3$$$ exceeds this limit, the local warlord confiscates $$$2$$$ of her guards without compensation. She leaves the first region with exactly $$$1$$$ guard. The cost for this step is $$$45$$$ coins.

Before entering the second region, Alice currently has $$$1$$$ guard. To safely navigate the danger level $$$D_2 = 2$$$, she chooses to hire $$$1$$$ additional guard, bringing her party size to $$$v = 2$$$. She pays a hiring fee of $$$10$$$ coins for the single new guard and a wage of $$$10$$$ coins for the $$$2$$$ guards currently in her party. She avoids the ambush and passes the martial limit safely since $$$2 \le 2$$$. The cost for this step is $$$20$$$ coins.

The total minimum cost to complete the journey is $$$45 + 20 = 65$$$ coins.