测试数据来自 system/1821

描述

已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大，而比它右儿子结点的数据值小。
另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。
已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。
一个结点在树中的深度定义为它到树根的距离加1。因此树的根结点的深度为1。
每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。
现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出K的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？

格式

输入格式

输入的第一行为两个正整数N，K(N<=70，1<=K<=30000000)。其中：N表示结点的个数，K表示每次修改所需的额外修改代价。
接下来的一行为N个非负整数，表示每个结点的数据值。
再接下来的一行为N个非负整数，表示每个结点的权值。
再接下来的一行为N个非负整数，表示每个结点的访问频度。
其中：所有的数据值、权值、访问频度均不超过400000。每两个数之间都有一个空格分隔，且行尾没有空格。

输出格式

输出仅一行为一个数，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

样例1

样例输入1

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

样例输出1

29

限制

每个测试点1s。

提示

输入的原图是图1，它的访问代价是：1×1+2×2+3×3+4×4=30。
最佳的修改方案是把输入中的第3个结点的权值改成0，得到图2，访问代价是：1×2+2×3+3×1+4×2=19，加上额外修改代价10，一共是29。

图1

图2

来源

NOI 2009 Day 1