Binary Search Tree

Suppose we’ve got a special BST ( Binary Search Tree ), according to the definition, all the nodes in this BST has a bigger value than its left child and, at the same time, smaller than its right child.
On the other hand, every node in this special BST has a weight. For every node, its weight is smaller than either of its child.
If every value is different and so is the weight, we can get an interesting conclusion, when all weights and values of the nodes are determined, the BST is determined as well. Because such a tree can be seen as a BST inserted in the order of weight and sorted by value.
Another common sense, the depth of a node is defined by one plus its distance to the root. So the root’s depth is one.
Well, it seems that this special BST is not special enough, obviously. I mean it’s just a normal BST plus heap’s characteristics. So I made it a little bit more difficult, only a little bit, trust me.
When dealing with a real-life problem, the access frequency of each node differs, and I’ll set it on the node. We call the access cost of a node as its access frequency multiplies the depth of it, and the access cost of an entire special BST as the sum of all access cost of its nodes.
Now, I’ll give you a data set contains all nodes’ value, weight and access frequency, and you can modify the weight of some nodes, but every modify operation needs K extra cost. You can modify the weight to any real number, however, after that, every weight must still be different from each other. Your task is pretty simple, tell what the minimum sum of the access cost of this special BST and the extra cost is after the modify operations.

The first line contains two positive integers N and K. N is the number of the nodes, and k is the extra cost needed for every modify operation. ( N<=70, 1<=K<=30000000 )
Next three lines, each line has N non-negative integers, indicate the value, weight and access frequency of each node separately. And all this integers are below or equal to 400000.

One number, the minimum sum according to the description.

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

29

2009 Multi-University Training Contest 19 - Host by BNU