#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Damian recently found an abandoned diamond mine, how fortunate! Unfortunately for him, digging is hard work, and he is running low on energy.

The mine can be modeled as a tree with *N* nodes, where each node represents a compartment of the mine, containing some value of diamond *V _{i}*, and each edge represents a partially caved-in tunnel.

Each tunnel will require a certain amount of energy *E _{i}* to excavate in order to access the other side. However, once excavated, no further energy will be needed to traverse to-and-fro that tunnel. Damian begins at compartment 0, the entrance.

What is the maximum value of diamond that Damian can pillage?

## Input

The first line contains two integers *N* and *K*, the number of nodes and the maximum amount of energy Damian can expend.

The second line contains *N* space-separated integers, with the *i*th integer representing the value of diamond present in compartment *i*.

The next *N* - 1 lines will contain 3 integers each, with each line representing the two nodes that the tunnel connects, followed by the amount of energy needed to excavate it.

## Output

The output should contain one line containing one integer, the maximum value of diamond that Damian can pillage from the mine.

## Limits

For all subtasks, 0 ≤ *E _{i}* ≤

*K*; 0 ≤

*V*≤ 10

_{i}^{5}.

Subtask 1 (11%): 1 ≤ *N*, *K* ≤ 3 000. All *E _{i}* = 0.

Subtask 2 (23%): 1 ≤ *N*, *K ≤* 3 000. All edges are connected to node 0.

Subtask 3 (47%): 1 ≤ *N*, *K ≤* 500.

Subtask 4 (19%): 1 ≤ *N*, *K ≤* 3 000.

Subtask 5 (0%): Sample Testcases.

## Sample Testcase 1

### Input

7 3 3 6 7 9 20 11 13 0 1 2 0 2 1 0 3 3 1 4 1 3 5 2 3 6 2

### Output

29

## Sample Output 1 Explanation

Damian excavates the 0-1 and 1-4 tunnels for a total energy cost of 2 + 1 = 3. With access to compartments 0, 1 and 4, the total value he can pillage is 3 + 6 + 20 = 29.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 11 | 6 | 1s | 256MB | Minimum |

2 | 23 | 6 | 1s | 256MB | Minimum |

3 | 47 | 6 | 1s | 256MB | Minimum |

4 | 19 | 6 | 1s | 256MB | Minimum |

5 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o excavation -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512