A special binary search tree is given. By definition, the data value of each node in this binary search tree is greater than the data values of the nodes in its left subtree and smaller than the data values of the nodes in its right subtree.

On the other hand, every node in this search tree has a weight, and the weight of each node is smaller than the weights of its child nodes.

It is known that all data values in the tree are distinct, and all weights in the tree are distinct. This leads to an interesting conclusion: if the data value and weight of every node in the tree are determined, the structure of the tree is uniquely determined. This is because such a tree can be viewed as a binary search tree obtained by inserting nodes in increasing order of their weights, where the nodes are ordered by their data values.

The depth of a node in the tree is defined as its distance from the root plus 1. Therefore, the depth of the root node is 1.

In addition to the data value and weight, each node has an access frequency. We define the access cost of a node in the tree as its access frequency multiplied by its depth in the tree. The access cost of the entire tree is defined as the sum of the access costs of all nodes in the tree.

Now, given the data value, weight, and access frequency of each node, you can modify the weights of some nodes as needed, but each modification incurs an additional modification cost of $K$. You can change the weight of a node to any real number, but after the modification, all nodes' weights must remain distinct. Your task is to find the minimum sum of the access cost of the entire tree and the total additional modification cost.

Input

The first line contains two positive integers $N$ and $K$. $N$ is the number of nodes, and $K$ is the additional modification cost required for each modification.

The next line contains $N$ non-negative integers, which are the data values of each node.

The next line contains $N$ non-negative integers, which are the weights of each node.

The next line contains $N$ non-negative integers, which are the access frequencies of each node.

All data values, weights, and access frequencies do not exceed $400000$. Each pair of numbers is separated by a space, and there are no spaces at the end of the lines.

Output

Output a single number, which is the minimum sum of the access cost of the entire tree and the total additional modification cost.

Examples

Input 1

4 10
1 2 3 4
1 2 3 4
1 2 3 4

Output 1

29

Note

The original tree for the input is the left figure, and its access cost is $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 30$. The optimal modification strategy is to change the weight of the 3rd node in the input to $0$, resulting in the right figure. The access cost is $1 \times 2 + 2 \times 3 + 3 \times 1 + 4 \times 2 = 19$. Adding the additional modification cost of $10$, the total is $29$.

Constraints

$40\%$ of the data satisfies $N \le 30$; $70\%$ of the data satisfies $N \le 50$; $100\%$ of the data satisfies $N \le 70, 1 \le K \le 30000000$.

Figure 1. The original tree