Weighted Binary Search Tree Reordering

We are given a special binary search tree with n nodes. Each node has three attributes: a data value (key), a weight and an access frequency. The tree satisfies two properties:

• The binary‐search tree (BST) property holds with respect to the data values: for any node, its data value is greater than that of its left child and smaller than that of its right child.
• Every node’s weight is less than the weights of its children. (All weights are distinct.)

Since the tree is uniquely determined by inserting nodes in the order of increasing weight into a BST (ordering by data value), if we know the data value and weight of each node the tree structure is fixed. In addition, each node has an access frequency, and the access cost of a node is defined as its frequency multiplied by its depth in the tree (where the depth of the root is 1 and the depth of any other node is the depth of its parent plus 1). The total cost of the tree is the sum of the access cost of all nodes.

You are allowed to change (i.e. reassign) the weights of some nodes at a price of K per modification. When you change the weight of a node you may assign it any real number; however, after all modifications, all nodes’ weights must remain distinct. Because you are able to choose the new weights arbitrarily, you have some freedom to alter the final tree structure (which is obtained by inserting the nodes in order of increasing weight into a BST according to their data values).

The goal is to choose a set of nodes (possibly empty) whose weights you will leave unchanged and to modify the weights of all the other nodes (each at cost K) such that the sum of the overall tree access cost plus the total modification cost is minimized.

It turns out that if a node’s weight is not modified then its relative order in the final sorted-by‐weight sequence is fixed. In other words, if two nodes are not modified and one originally had a smaller weight than the other, then it must remain so in the new weights. We call a node whose weight is not modified a fixed node and a node whose weight is modified a modified node.

Define the optimal cost as

[ \text{Optimal Cost} = \text{(total access cost of the BST built from the chosen weight permutation)} + K \times \text{(number of modified nodes)}, ]

where the BST is built by inserting the nodes (in increasing order of their final weights) into an initially empty BST (using the data values for the BST property), and the access cost of a node is its frequency multiplied by its depth in the tree.

Input Format: The first line contains two integers n and K (1 ≤ n ≤ 15). Each of the next n lines contains three integers: data, weight and frequency. All data values and weights are distinct.

Output Format: Output one integer, which is the minimal possible sum of the tree access cost and the total modification cost.

Note (with LaTeX): The depth of a node is defined as its distance from the root plus \(1\). Thus, the root has depth \(1\). The classical optimal binary search tree recurrence (when there are no constraints on the permutation) is given by:

[ \text{dp}(i,j) = \sum_{k=i}^{j} f_k + \min_{r=i}^{j} \Bigl( \text{dp}(i,r-1) + \text{dp}(r+1,j) \Bigr), \quad \text{dp}(i,j)=0 \text{ if } i>j. ]

When some nodes are fixed their relative order (according to their original weight) is forced. In any interval, if there is at least one fixed node then the allowed candidate for the root is the fixed node with the smallest original weight in that interval.

inputFormat

The input begins with a line containing two integers: n (the number of nodes, 1 ≤ n ≤ 15) and K (the modification cost per node). Each of the next n lines contains three integers: data (the node’s key), weight (the node’s weight) and frequency (the node’s access frequency). All data values and weights are distinct.

outputFormat

Output a single integer, the minimal total cost, which is the sum of the access cost in the BST and the total modification cost.

sample

2 5
10 10 1
20 100 100

107